leetcode-374

题目

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

Example 1:
1
2
3
> Input: nums = [1, 5, 1, 1, 6, 4]
> Output: One possible answer is [1, 4, 1, 5, 1, 6].
>

Example 2：

1
2
3

> 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.

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

分析

这道题的意思是把一个无序的数组进行摆动排序，即在奇数下标(1, 3, 5, …)的元素值大于它相邻的偶数下标(0, 2, 4, …)的元素值。如果画出元素值大小随下标变化的图像的话，图像就随着下标的增大在上下不断摆动。

题目保证给出的输入一定有对应有效的输出。

我认为这道题的难点主要在于输入的值中可能有很多相同的值，如果值各异的话，通过简单的遍历来进行值的交换即可，每次遍历到的元素只需要与已确定的部分的最后一个元素比较大小。但由于存在相同的值，这种方法会导致相同的值会聚集在一起，无法得到正确结果。

解法一

一种比较容易想到的解法是先找到数组的中位数，然后把所有大于中位数的元素放在奇数位置，所有小于中位数的元素放在偶数位置，等于中位数的元素则需要好好考虑，要尽量把它们分开来存放，如果两个等于中位数的元素相邻也是不满足要求的。

首先把数组排序，就能够找到中位数，然后把大于中位数的元素从左往右开始存放到奇数位置，把小于中位数的元素从右往左存放到偶数位置，等于中位数的元素存放在剩余位置。由于数组已经排好序，所以对于奇数位置，等于中位数的元素是放在右边的，而对于偶数位置，等于中位数的元素是放在左边的，这样就一定能够满足要求。所以寻找中位数不能使用nth_element()函数，因为这个函数并不会把数组排序，之后的操作也就无法保证能把等于中位数的元素分离开。

这种解法时间复杂度为排序的复杂度，O(nlogn)，空间复杂度O(n)。

代码

class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        //nth_element(nums.begin(), nums.begin() + nums.size() / 2, nums.end());
        int len = nums.size();
        int mid = nums[len /  2];
        int odd = 1, even = (len % 2) ? len - 1 : len - 2;
        vector<int> tmp(len, mid);
        for(int i = len - 1; i > len / 2; i--) {
            tmp[odd] = nums[i];
            odd += 2;
        }
        for(int i = 0; i < len / 2; i++) {
            tmp[even] = nums[i];
            even -= 2;
        }
        nums = tmp;
    }
};

解法二

解法一的时间复杂度和空间复杂度都不是最优的，在Discuss中有人给出了时间复杂度O(n)，空间复杂度O(1)的解法，用到了virtual indexing和three-way-partition的技巧。

主要想法跟解法一类似，都是去找中位数，然后把大于中位数的元素放奇数位置，小于中位数的元素放偶数位置，等于中位数的元素放在剩余位置。

要解决时间复杂度的问题，可以用nth_element()函数来寻找中位数；要解决空间复杂度的问题，就不能够构造另外的数组，要进行就地置换(in_place)。

现在总结一下需要解决的问题：大于中位数的放1, 3, 5,…位置，小于中位数的放2, 4, 6,…位置，等于中位数的位置可以不变，同时在交换位置的过程中不能开辟额外的内存空间。

通过结合下标映射和3分法可以解决问题：把下标映射成1，3，5，…，2， 4， 6，…的形式，然后利用3分法，大于中位数的放左边，即映射后的1，3， 5，…下标；小于中位数的放右边，即映射后的2，4，6…下标。

映射是return (1 + 2 * index) % (len | 1);，其中len | 1在len为偶数时取len + 1，在len为奇数时取len。映射把从0～len - 1的index映射到1, 3, 5, …, 2, 4, 6, …。

之后就交给三分法来解决问题，只不过用于三分法的数组下标始终是经过映射后得到的下标。

时间复杂度为O(n)，空间复杂度为O(1)。

代码

class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        nth_element(nums.begin(), nums.begin() + nums.size() / 2, nums.end());
        int len = nums.size();
        int mid = nums[len / 2];

        for (int i = 0, left = 0, right = len - 1; i <= right;) {
            if (nums[mappedIndex(i, len)] > mid) swap(nums, mappedIndex(left++, len), mappedIndex(i++, len));
            else if (nums[mappedIndex(i, len)] < mid) swap(nums, mappedIndex(right--, len), mappedIndex(i, len));
            else i++;
        }
    }

private:
    void swap(vector<int>& nums, int index1, int index2) {
        int tmp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = tmp;
    }
    //把从0～len - 1的index映射到1, 3, 5, ..., 2, 4, 6, ...
    int mappedIndex(int index, int len) {
        return (1 + 2 * index) % (len | 1);
    }
};