# C++, O(n) time, O(1) extra space. Find median.

• class Solution {
public:
void wiggleSort(vector<int>& nums) {
if (nums.size() <= 1) return;

``````    int left = 0, right = nums.size(), target = (nums.size() + 1) / 2;
int re;
while (true) {
int t = nums[left], l = left, r = right;
while (l < r) {
if (nums[l] <= t) l++;
else swap(nums[l], nums[--r]);
}
l--;
swap(nums[left], nums[l]);
if (target == l - left + 1) {
re = nums[l];
break;
}
else if (target < l - left + 1) {
right = l;
}
else {
target -= l - left + 1;
left = l + 1;
}
}

left = 0;
right = nums.size() - 1;
if (right % 2 == 0) right--;

for (int i = left; i < nums.size(); i += 2) {
if (nums[i] < re) {
nums[left] = nums[i];
left += 2;
}
else if (nums[i] > re) {
swap(nums[i], nums[right]);
right -= 2;
i -= 2;
}
}

for (int i = right; i >= 0; i -= 2) {
if (nums[i] < re) {
nums[left] = nums[i];
left += 2;
}
else if (nums[i] > re) {
nums[right] = nums[i];
right -= 2;
}
}

for (; left < nums.size(); left += 2) nums[left] = re;
for (; right >= 0; right -= 2) nums[right] = re;
}
``````

};

• You're using simple quickselect which is only O(n^2) and not O(n), no?

Btw, your "`vector& nums`" causes a compile error.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.