Leetcode 324: Wiggle Sort II

Input: nums = [1,5,1,1,6,4]
Output: [1,6,1,5,1,4]
Explanation: [1,4,1,5,1,6] is also accepted.
Input: nums = [1,3,2,2,3,1]
Output: [2,3,1,3,1,2]
class Solution {
public:
void wiggleSort(vector<int>& nums) {
auto it = nums.begin() + nums.size() / 2;
nth_element(nums.begin(), it, nums.end());
int tmp = *it;
#define A(i) nums[(1 + 2 * (i)) % (nums.size() | 1)]
int i = 0, j = 0, k = nums.size() - 1;
while (j <= k) {
if (A(j) > tmp) swap(A(i++), A(j++));
else if (A(j) < tmp) swap(A(k--), A(j));
else ++j;
}
}
};

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store