【324. 摆动排序 II】

来源：力扣（LeetCode）

描述：

给你一个整数数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]... 的顺序。

你可以假设所有输入数组都可以得到满足题目要求的结果。

示例 1：

输入：nums = [1,5,1,1,6,4]
输出：[1,6,1,5,1,4]
解释：[1,4,1,5,1,6] 同样是符合题目要求的结果，可以被判题程序接受。
1
2
3

示例 2：

输入：nums = [1,3,2,2,3,1]
输出：[2,3,1,3,1,2]
1
2

提示：

• 1 <= nums.length <= 5 * 10⁴
• 0 <= nums[i] <= 5000
• 题目数据保证，对于给定的输入 nums ，总能产生满足题目要求的结果

方法一：排序

思路与算法

代码:

class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        int n = nums.size();
        vector<int> arr = nums;
        sort(arr.begin(), arr.end());
        int x = (n + 1) / 2;
        for (int i = 0, j = x - 1, k = n - 1; i < n; i += 2, j--, k--) {
            nums[i] = arr[j];
            if (i + 1 < n) {
                nums[i + 1] = arr[k];
            }
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

执行用时：8 ms, 在所有 C++ 提交中击败了99.09%的用户
内存消耗：17.3 MB，在所有 C++ 提交中击败了35.37%的用户
复杂度分析
时间复杂度： O(nlogn)，其中 n 为数组的长度。数组排序的时间复杂度为 O(nlogn)，遍历数组的时间复杂度为 O(n)，总的时间复杂度为 O(nlogn)。
空间复杂度： O(n)，其中 n 为数组的长度。需要对原数组进行拷贝一次，需要的空间为 O(n)。

方法二：三向切分

思路与算法

代码:

class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        int n = nums.size();
        int x = (n + 1) / 2;
        int mid = x - 1;
        nth_element(nums.begin(), nums.begin() + mid, nums.end());
        for (int k = 0, i = 0, j = n - 1; k <= j; k++) {
            if (nums[k] > nums[mid]) {
                while (j > k && nums[j] > nums[mid]) {
                    j--;
                }
                swap(nums[k], nums[j--]);
            }
            if (nums[k] < nums[mid]) {
                swap(nums[k], nums[i++]);
            }
        }
        vector<int> arr = nums;
        for (int i = 0, j = x - 1, k = n - 1; i < n; i += 2, j--, k--) {
            nums[i] = arr[j];
            if (i + 1 < n) {
                nums[i + 1] = arr[k];
            }
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

执行用时：16 ms, 在所有 C++ 提交中击败了75.61%的用户
内存消耗：17.1 MB, 在所有 C++ 提交中击败了78.20%的用户
复杂度分析
时间复杂度： O(n)，其中 n 为数组的长度。找到数组中排序为 k 的数需要的时间复杂度为 O(n)，对数组进行三向切分需要的时间复杂度为 O(n)，对数组进行摆放的时间的复杂度为 O(n)，总的时间复杂度为 O(n)。
空间复杂度： O(n)，其中 n 为数组的长度。需要对原数组进行拷贝一次，需要的空间为 O(n)。

方法三：索引转换

思路与算法

代码:

class Solution {
public:
    inline int transAddress(int i, int n) {
        return (2 * n - 2 * i - 1) % (n | 1);
    }

    void wiggleSort(vector<int>& nums) {
        int n = nums.size();
        int x = (n + 1) / 2;
        int mid = x - 1;
        nth_element(nums.begin(), nums.begin() + mid, nums.end());
        int target = nums[mid];
        for (int k = 0, i = 0, j = n - 1; k <= j; k++) {
            if (nums[transAddress(k, n)] > target) {
                while (j > k && nums[transAddress(j, n)] > target) {
                    j--;
                }
                swap(nums[transAddress(k, n)], nums[transAddress(j--, n)]);
            }
            if (nums[transAddress(k, n)] < target) {
                swap(nums[transAddress(k, n)], nums[transAddress(i++, n)]);
            }
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

执行用时：8 ms, 在所有 C++ 提交中击败了99.09%的用户
内存消耗：16.8 MB, 在所有 C++ 提交中击败了90.93%的用户
复杂度分析
时间复杂度： O(n)，其中 n 为数组的长度。找到数组中排序为 k 的数需要的时间复杂度为 O(n)，对数组进行三向切分需要的时间复杂度为 O(n)，总的时间复杂度为 O(n)。
空间复杂度： O(logn)。查找第 k 大的元素时需要使用递归，此时递归使用栈空间的空间代价的期望为 O(logn)。

方法四：递归优化

思路与算法

我们可以在方法三的基础上对查找数组中排序为第 k 大元素的函数进行优化，用非递归实现查找第 k 大的元素，进一步优化空间复杂度。

代码：

class Solution {
public:
    int partitionAroundPivot(int left, int right, int pivot, vector<int> &nums) {
        int pivotValue = nums[pivot];
        int newPivot = left;
        swap(nums[pivot], nums[right]);
        for (int i = left; i < right; ++i) {
            if (nums[i] > pivotValue) {
                swap(nums[i], nums[newPivot++]);
            }
        }
        swap(nums[right], nums[newPivot]);
        return newPivot;
    }

    int findKthLargest(vector<int> &nums, int k) {
        int left = 0, right = nums.size() - 1;
        default_random_engine gen((random_device())());
        while (left <= right) {
            uniform_int_distribution<int> dis(left, right);
            int pivot = dis(gen);
            int newPivot = partitionAroundPivot(left, right, pivot, nums);
            if (newPivot == k - 1) {
                return nums[newPivot];
            } else if (newPivot > k - 1) {
                right = newPivot - 1;
            } else { 
                left = newPivot + 1;
            }
        }
        return nums[k - 1];
    }

    inline int transAddress(int i, int n) {
        return (2 * n - 2 * i - 1) % (n | 1);
    }

    void wiggleSort(vector<int>& nums) {
        int n = nums.size();
        int x = (n + 1) / 2;
        int mid = x - 1;
        int target = findKthLargest(nums, n - mid);
        for (int k = 0, i = 0, j = n - 1; k <= j; k++) {
            if (nums[transAddress(k, n)] > target) {
                while (j > k && nums[transAddress(j, n)] > target) {
                    j--;
                }
                swap(nums[transAddress(k, n)], nums[transAddress(j--, n)]);
            }
            if (nums[transAddress(k, n)] < target) {
                swap(nums[transAddress(k, n)], nums[transAddress(i++, n)]);
            }
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

执行用时：168 ms, 在所有 C++ 提交中击败了11.66%的用户
内存消耗：16.9 MB, 在所有 C++ 提交中击败了86.81%的用户
复杂度分析
时间复杂度： O(n)，其中 n 为数组的长度。找到数组中排序为 k 的数需要的时间复杂度为 O(n)，对数组进行三向切分需要的时间复杂度为 O(n)，总的时间复杂度为 O(n)。
空间复杂度： O(1)。