Wiggle Sort II ใน C ++

สมมติว่าเรามี nums อาร์เรย์ที่ไม่ได้เรียงลำดับ เราต้องจัดเรียงใหม่เพื่อให้ nums[0] nums[2]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• สร้างหนึ่งอาร์เรย์ x ที่มีองค์ประกอบเหมือนกับ nums

• เรียงลำดับ x อาร์เรย์

• i :=size of x – 1, j :=(size of x – 1) / 2 and n :=size of nums array

• สำหรับ l ในช่วง 0 ถึง n – 1 ให้เพิ่ม l ขึ้น 2 ในแต่ละขั้นตอน

  • nums[l] :=x[j]

  • ลด j โดย 1

• สำหรับ l ในช่วง 1 ถึง n – 1 ให้เพิ่ม 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, ]