ধরা যাক একটি অনসর্টেড অ্যারে 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 অ্যারের আকার
l = 0 থেকে n-1 পর্যন্ত, প্রতিটি স্টেপে l ২ বাড়িয়ে
nums[l] := x[j]
j ১ কমানো
l = 1 থেকে n-1 পর্যন্ত, প্রতিটি স্টেপে l ২ বাড়িয়ে
nums[l] := x[i]
i ১ কমানো
নিচের ইমপ্লিমেন্টেশন দেখুন −
উদাহরণ
#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, ]
