在C ++中摆动Sort II

假设我们有一个未排序的数组nums，我们必须重新排列它，使nums [0] <nums [1]> nums [2] <nums [3]。因此，如果输入类似于[1,5,1,1,6,4]，则输出将为[1,4,1,5,1,6]。

为了解决这个问题，我们将遵循以下步骤-

• 制作一个数组x，其元素与nums相同

• 排序x数组

• i：= x的大小– 1，j：=（x的大小– 1）/ 2和n：= nums数组的大小

• 对于范围从0到n – 1的l，每步将l增加2

• nums [l]：= x [j]

• 将j减1

• 对于范围从1到n – 1的l，每步将l增加2

• nums [l]：= x [i]

• 将我减1

让我们看下面的实现以更好地理解-

示例

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   void wiggleSort(vector<int>& nums) {
      vector <int> x(nums);
      sort(x.begin(), x.end());
      int i = x.size() - 1 ;
      int j = (x.size() - 1)/2;
      int n = nums.size();
      for(int l = 0; l < n; l +=2){
         nums[l] = x[j--];
      }
      for(int l = 1; l < n; l +=2){
         nums[l] = x[i--];
      }
   }
};
main(){
   vector<int> v = {1,5,1,1,6,4};
   Solution ob;
   (ob.wiggleSort(v));
   print_vector(v);
}

输入项

[1,5,1,1,6,4]

输出结果

[1, 6, 1, 5, 1, 4, ]