题目描述
给定一个无序的数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]... 的顺序。
示例 1:
输入:nums = [1, 5, 1, 1, 6, 4]输出: 一个可能的答案是[1, 4, 1, 5, 1, 6]
示例 2:
输入:nums = [1, 3, 2, 2, 3, 1]输出: 一个可能的答案是[2, 3, 1, 3, 1, 2]
说明:
你可以假设所有输入都会得到有效的结果。
进阶:
你能用 O(n) 时间复杂度和 / 或原地 O(1) 额外空间来实现吗？
https://leetcode-cn.com/problems/wiggle-sort-ii/
解法1 – 使用排序O(nlogn)
解法1采用一个trick，我们先对数组nums排序，然后将数组分为两半，记做nums[0…lowerEnd], nums[lowerEnd+1…higherEnd]，其中lowerEnd = (|nums| – 1) / 2, higherEnd = |nums| – 1。
然后我们交替的将lowerEnd与higherEnd指向的元素写入结果数组中，使得higherEnd指向的元素写入到结果数组的奇数索引位置，使得lowerEnd指向的元素写入到数组偶数索引位置。
我们注意两个细节，第一是为什么要让higherEnd写入奇数索引？第二是为什么要逆序？举个例子nums = {1, 2, 3}，计算lowerEnd = (3 – 1) / 2 = 1, higherEnd = 3 – 1 = 2，如果我们让higherEnd指向的元素写入奇数索引的位置能够得到结果{2, 3, 1}这是正确的摆动序列；如果我们让higherEnd指向的元素写入偶数索引的位置，那么会得到{3, 2, 1}。可以看到，这是一个递减的序列是不正确的。为了形象的理解，我们将摆动序列视为山峰山谷。那么大的元素应该在山峰位置，左右两边伴随着山谷，这就是为什么大的元素应该放在奇数索引位置。
第二，为什么要逆序写入？因为逆序写入会使得相同元素离得尽可能远。例如序列nums = {1, 1, 2, 2, 2, 2, 3, 3}，len = 8，lowerEnd = (8 – 1) / 2 = 3, higherEnd = 8 – 1 = 7，我们按照逆序的方式写入到结果数组能够得到{2, 3, 2, 3, 1, 2, 1, 2}，我们观察到结果数组第一个2来源lowerEnd指向nums数组的左半部分，最后一个2来源于右半部分，逆序写入会这使得左半部分较大的数优先写入；右半部分较小的数最后写入。而左半部分较大的数和右半部分较小的数是相邻的，逆序写入就可以避免重复的元素依次出现。如果我们按照顺序的方式写入，将会得到错误的结果{1, 2, 1, 2, 2, 3, 2, 3}，可以看到2连续出现了两次。
该方法需要排序，因此时间复杂度为O(nlogn)；需要拷贝原始数组，因此空间复杂度为O(n)。全部代码如下：
import java.util.Arrays;
class Solution {
public void wiggleSort(int[] nums) {
if (nums == null || nums.length == 0)
return;
int lowerEnd = (nums.length - 1) / 2;
int higherEnd = nums.length - 1;
int[] copy = Arrays.copyOf(nums, nums.length);
int k = 0;
Arrays.sort(copy);
while (lowerEnd >= 0 || higherEnd > (nums.length - 1) / 2) {
if (lowerEnd >= 0 && higherEnd > (nums.length - 1) / 2) {
if (k % 2 == 0) {
nums[k++] = copy[lowerEnd--];
} else {
nums[k++] = copy[higherEnd--];
}
} else if (lowerEnd >= 0)
nums[k++] = copy[lowerEnd--];
else
nums[k++] = copy[higherEnd--];
}
}
}
解法2 – 根据中位数重新写入 O(n)
我们首先求得数组nums的中位数median，将nums分为两部分lowerNums与higherNums，且0<=|lowerNums| – |higherNums|<=1。如果元素小于median，将它放入lowerNums；如果元素大于median，将它放入higherNums；如果元素就是median，那么将它放入lowerNums与higherNums，使得0<=|lowerNums| – |higherNums|<=1。
当我们构建完lowerNums与higherNums数组后，我们将他们回填到nums数组。逆序访问lowerNums，将lowerNums的元素放入nums偶数索引位置；将higherNums放入nums奇数索引位置。逆序访问lowerNums的原因和解法1一样，使得lowerNums与higherNums中相同的元素离得尽可能远。
该方法的时间复杂度O(n)，空间复杂度O(n)。全部代码如下：
import java.util.Random;
class Solution {
private void shuffle(int[] nums) {
Random random = new Random();
for (int i = 1; i < nums.length; i++) {
int j = random.nextInt(i + 1);
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
// k start with 1
int findKth(int[] nums, int start, int end, int k) {
if (start >= end)
return nums[start];
int pivot = nums[end];
int i = start;
for (int j = start; j < end; j++) {
if (nums[j] <= pivot) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
i++;
}
}
int tmp = nums[i];
nums[i] = nums[end];
nums[end] = tmp;
if (i == k - 1)
return nums[i];
else if (i > k - 1)
return findKth(nums, start, i - 1, k);
else
return findKth(nums, i + 1, end, k);
}
public void wiggleSort(int[] nums) {
if (nums == null || nums.length < 2)
return;
int higherLen = nums.length / 2;
int lowerLen = nums.length - higherLen;
// we keeping 0 <= leftLen - rightLen <= 1
int[] lowerNums = new int[lowerLen];
int[] higherNums = new int[higherLen];
int i = 0, j = 0;
shuffle(nums);
int median = findKth(nums, 0, nums.length - 1, nums.length / 2 + 1);
for (int num : nums) {
if (num < median) {
lowerNums[i++] = num;
} else if (num > median)
higherNums[j++] = num;
}
while (i < lowerLen) {
lowerNums[i++] = median;
}
while (j < higherLen) {
higherNums[j++] = median;
}
// we reversely write out lowerNums,
// otherwise the medians in the lowerNums may meet the medians in the higherNums
for (int idx = 0; idx < lowerLen; idx++)
nums[2 * idx] = lowerNums[lowerLen - idx - 1];
for (int idx = 0; idx < higherLen; idx++)
nums[2 * idx + 1] = higherNums[idx];
}
}
参考：