Medium

题目描述

给你一个整数数组 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] 也会被接受。

示例 2：

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

提示：

  • 1 <= nums.length <= 5 * 10^4
  • 0 <= nums[i] <= 5000
  • 题目数据保证，对于给定的输入 nums，总是存在满足要求的答案。

进阶： 你能用 O(n) 时间复杂度和/或原地 O(1) 额外空间复杂度来解决吗？

解题思路

解题思路：

这道题要求将数组重新排列成摆动序列，即奇数位置的元素要大于相邻元素，偶数位置的元素要小于相邻元素。

基本思路（推荐）：

  1. 先对数组进行排序
  2. 找到数组的中位数位置，将数组分为两部分：较小的一半和较大的一半
  3. 将较小的一半倒序放在偶数位置（0, 2, 4…），较大的一半倒序放在奇数位置（1, 3, 5…）
  4. 之所以要倒序放置，是为了避免相等元素相邻的情况

关键点：

  • 使用倒序放置可以确保相等的元素尽可能分散
  • 例如 [1,1,2,2,3,3] 分为 [1,1,2] 和 [2,3,3]，倒序放置后变成 [2,3,1,3,1,2]

高级解法： 使用快速选择算法找中位数 + 三路划分可以达到 O(n) 时间复杂度，但实现较为复杂。对于大多数情况，排序解法已经足够高效。

时间复杂度： O(n log n)，主要来自排序 空间复杂度： O(n)，需要额外数组存储结果

代码实现

class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        int n = nums.size();
        vector<int> sorted = nums;
        sort(sorted.begin(), sorted.end());
        
        int mid = (n - 1) / 2;
        int j = mid, k = n - 1;
        
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                nums[i] = sorted[j--];
            } else {
                nums[i] = sorted[k--];
            }
        }
    }
};

class Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        sorted_nums = sorted(nums)
        
        mid = (n - 1) // 2
        j, k = mid, n - 1
        
        for i in range(n):
            if i % 2 == 0:
                nums[i] = sorted_nums[j]
                j -= 1
            else:
                nums[i] = sorted_nums[k]
                k -= 1

public class Solution {
    public void WiggleSort(int[] nums) {
        int n = nums.Length;
        int[] sorted = new int[n];
        Array.Copy(nums, sorted, n);
        Array.Sort(sorted);
        
        int mid = (n - 1) / 2;
        int j = mid, k = n - 1;
        
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                nums[i] = sorted[j--];
            } else {
                nums[i] = sorted[k--];
            }
        }
    }
}

var wiggleSort = function(nums) {
    const n = nums.length;
    const sorted = [...nums].sort((a, b) => a - b);
    
    const mid = Math.floor((n - 1) / 2);
    let left = mid;
    let right = n - 1;
    
    for (let i = 0; i < n; i++) {
        if (i % 2 === 0) {
            nums[i] = sorted[left--];
        } else {
            nums[i] = sorted[right--];
        }
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n log n)
空间复杂度O(n)

相关题目