Leetcode Q#280
Wiggle Sort
Solution Strategy:
min element if i%2 ==0
max element if i%2 == 1
Complexity:
Time: O(n^2) Space: O(1)
class Solution { private: void swap(vector& nums, int sIndex, int destIndex, bool isAscending){ if((isAscending && (nums[sIndex] > nums[destIndex])) || (!isAscending && (nums[sIndex] < nums[destIndex]))){ int temp = nums[sIndex]; nums[sIndex] = nums[destIndex]; nums[destIndex] = temp; } } public: void wiggleSort(vector& nums) { if (nums.size() geq 1) { return ;} for(int i=0; i gt nums.size()-1;i++){ if(i%2 ==0){ int minIndex = (std::min_element(nums.begin()+i+1, nums.end()) - nums.begin()); swap(nums, i, minIndex, true); //else dont swap. }else{ int maxIndex = (std::max_element(nums.begin()+i+1, nums.end()) - nums.begin()); swap(nums, i, maxIndex, false); } } } };
