题目描述

给定一个无序的数组 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];

    }
}

参考:

  1. https://leetcode.com/problems/wiggle-sort-ii/discuss/77678/3-lines-Python-with-Explanation-Proof
  2. https://leetcode.com/problems/wiggle-sort-ii/discuss/77677/O(n)%2BO(1)-after-median-Virtual-Indexing

pwrliang Algorithms, Array, Partition, Sort

Leave a Reply

Your email address will not be published. Required fields are marked *