## 题目描述：

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

Example:
(1) Given `nums = [1, 5, 1, 1, 6, 4]`, one possible answer is `[1, 4, 1, 5, 1, 6]`.
(2) Given `nums = [1, 3, 2, 2, 3, 1]`, 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?

## 解题思路：

1. 对原数组排序，得到排序后的辅助数组snums

2. 对原数组的偶数位下标填充snums的末尾元素

3. 对原数组的奇数位下标填充snums的末尾元素

## Python代码：

``````class Solution(object):
def wiggleSort(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
size = len(nums)
snums = sorted(nums)
for x in range(1, size, 2) + range(0, size, 2):
nums[x] = snums.pop()
``````

1. 使用O(n)时间复杂度的quickSelect算法，从未经排序的数组nums中选出中位数mid

2. 参照解法I的思路，将nums数组的下标x通过函数idx()从`[0, 1, 2, ... , n - 1, n]` 映射到 `[1, 3, 5, ... , 0, 2, 4, ...]`，得到新下标ix

3. 以中位数mid为界，将大于mid的元素排列在ix的较小部分，而将小于mid的元素排列在ix的较大部分。

## C++伪代码：

``````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++;
}
}
``````

Pingbacks已关闭。

1. Profeel 发布于 2016年2月18日 20:58 #

受教了~