# [LeetCode] 324. Wiggle Sort II 摆动排序 II

2021年09月15日 阅读数：1

Given an unsorted array `nums`, reorder it such that `nums[0] < nums[1] > nums[2] < nums[3]...`.html

Example 1:java

```Input: `nums = [1, 5, 1, 1, 6, 4]`
Output: One possible answer is `[1, 4, 1, 5, 1, 6]`.```

Example 2:python

```Input: `nums = [1, 3, 2, 2, 3, 1]`
Output: One possible answer is `[2, 3, 1, 3, 1, 2]`.```

Note:
You may assume all input has valid answer.算法

Can you do it in O(n) time and/or in-place with O(1) extra space?数组

280. Wiggle Sort 的变形，这题`nums[0] < nums[1] > nums[2] < nums[3]...`.里面没有等号。 dom

Java:spa

```public void wiggleSort(int[] nums) {
int median = findKthLargest(nums, (nums.length + 1) / 2);
int n = nums.length;

int left = 0, i = 0, right = n - 1;

while (i <= right) {

if (nums[newIndex(i,n)] > median) {
swap(nums, newIndex(left++,n), newIndex(i++,n));
}
else if (nums[newIndex(i,n)] < median) {
swap(nums, newIndex(right--,n), newIndex(i,n));
}
else {
i++;
}
}

}

private int newIndex(int index, int n) {
return (1 + 2*index) % (n | 1);
}
```

Java:

```void wiggleSort(vector<int>& nums) {
int n = nums.size();

// Find a median.
auto midptr = nums.begin() + n / 2;
nth_element(nums.begin(), midptr, nums.end());
int mid = *midptr;

// Index-rewiring.
#define A(i) nums[(1+2*(i)) % (n|1)]

// 3-way-partition-to-wiggly in O(n) time with O(1) space.
int i = 0, j = 0, k = n - 1;
while (j <= k) {
if (A(j) > mid)
swap(A(i++), A(j++));
else if (A(j) < mid)
swap(A(j), A(k--));
else
j++;
}
}
```

Java:

```public class Solution {
public void wiggleSort(int[] nums) {
int medium = findMedium(nums, 0, nums.length - 1, (nums.length + 1) >> 1);
int s = 0, t = nums.length - 1 , mid_index = (nums.length + 1) >> 1;
int[] temp = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
if (nums[i] < medium)
temp[s++] = nums[i];
else if (nums[i] > medium)
temp[t--] = nums[i];
}

while (s < mid_index) temp[s++] = medium;
while (t >= mid_index) temp[t--] = medium;

t = nums.length;
for (int i = 0; i < nums.length; i++)
nums[i] = (i & 1) == 0 ? temp[--s] : temp[--t];
}

private int findMedium(int[] nums, int L, int R, int k) {
if (L >= R) return nums[R];
int i = partition(nums, L, R);
int cnt = i - L + 1;
if (cnt == k) return nums[i];
return cnt > k ? findMedium(nums, L, i - 1, k) : findMedium(nums, i + 1, R, k - cnt);
}

private int partition(int[] nums, int L, int R) {
int val = nums[L];
int i = L, j = R + 1;
while (true) {
while (++i < R && nums[i] < val) ;
while (--j > L && nums[j] > val) ;
if (i >= j) break;
swap(nums, i, j);
}
swap(nums, L, j);
return j;
}

private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}　　```

Python：

```# Time:  O(nlogn)
# Space: O(n)
# Sorting and reoder solution. (92ms)
class Solution(object):
def wiggleSort(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
nums.sort()
med = (len(nums) - 1) / 2
nums[::2], nums[1::2] = nums[med::-1], nums[:med:-1]　　```

Python:

```# Time:  O(n) ~ O(n^2)
# Space: O(1)
# Tri Partition (aka Dutch National Flag Problem) with virtual index solution. (TLE)
from random import randint
class Solution2(object):
def wiggleSort(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
def findKthLargest(nums, k):
left, right = 0, len(nums) - 1
while left <= right:
pivot_idx = randint(left, right)
new_pivot_idx = partitionAroundPivot(left, right, pivot_idx, nums)
if new_pivot_idx == k - 1:
return nums[new_pivot_idx]
elif new_pivot_idx > k - 1:
right = new_pivot_idx - 1
else:  # new_pivot_idx < k - 1.
left = new_pivot_idx + 1

def partitionAroundPivot(left, right, pivot_idx, nums):
pivot_value = nums[pivot_idx]
new_pivot_idx = left
nums[pivot_idx], nums[right] = nums[right], nums[pivot_idx]
for i in xrange(left, right):
if nums[i] > pivot_value:
nums[i], nums[new_pivot_idx] = nums[new_pivot_idx], nums[i]
new_pivot_idx += 1
nums[right], nums[new_pivot_idx] = nums[new_pivot_idx], nums[right]
return new_pivot_idx

def reversedTriPartitionWithVI(nums, val):
def idx(i, N):
return (1 + 2 * (i)) % N

N = len(nums) / 2 * 2 + 1
i, j, n = 0, 0, len(nums) - 1
while j <= n:
if nums[idx(j, N)] > val:
nums[idx(i, N)], nums[idx(j, N)] = nums[idx(j, N)], nums[idx(i, N)]
i += 1
j += 1
elif nums[idx(j, N)] < val:
nums[idx(j, N)], nums[idx(n, N)] = nums[idx(n, N)], nums[idx(j, N)]
n -= 1
else:
j += 1

mid = (len(nums) - 1) / 2
findKthLargest(nums, mid + 1)
reversedTriPartitionWithVI(nums, nums[mid])```

C++:

```// O(n) space
class Solution {
public:
void wiggleSort(vector<int>& nums) {
vector<int> tmp = nums;
int n = nums.size(), k = (n + 1) / 2, j = n;
sort(tmp.begin(), tmp.end());
for (int i = 0; i < n; ++i) {
nums[i] = i & 1 ? tmp[--j] : tmp[--k];
}
}
};　　```

C++:

```// O(1) space
class Solution {
public:
void wiggleSort(vector<int>& nums) {
#define A(i) nums[(1 + 2 * i) % (n | 1)]
int n = nums.size(), i = 0, j = 0, k = n - 1;
auto midptr = nums.begin() + n / 2;
nth_element(nums.begin(), midptr, nums.end());
int mid = *midptr;
while (j <= k) {
if (A(j) > mid) swap(A(i++), A(j++));
else if (A(j) < mid) swap(A(j), A(k--));
else ++j;
}
}
};
```

[LeetCode] 280. Wiggle Sort 摆动排序

[LeetCode] 75. Sort Colors 颜色排序