C++でのWiggleSortII

ソートされていない配列numsがあるとすると、nums [0] nums [2]

これを解決するには、次の手順に従います-

• numsと同じ要素を持つ1つの配列xを作成します

• 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]

  • 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, ]