C++ তে Wiggle Sort II

ধরুন আমাদের একটি সাজানো না করা অ্যারে সংখ্যা আছে, আমাদের এটিকে এমনভাবে সাজাতে হবে যাতে nums[0] nums[2]

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি অ্যারে x তৈরি করুন, যেটিতে সংখ্যার মতো একই উপাদান রয়েছে

• বাছাই x অ্যারে

• i :=x – 1 এর আকার, j :=(x – 1 এর আকার) / 2 এবং n :=সংখ্যা বিন্যাসের আকার

• 0 থেকে n – 1 পরিসরের জন্য, প্রতিটি ধাপে l 2 দ্বারা বাড়ান

  • সংখ্যা[l] :=x[j]

  • 1 দ্বারা j হ্রাস করুন

• 1 থেকে n – 1 পর্যন্ত l এর জন্য, প্রতিটি ধাপে l 2 দ্বারা বাড়ান

  • সংখ্যা[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, ]