江川个人博客FIELD NOTES / 个人知识库

Article / 文章

LeetCode 第324题：摆动排序 II

给你一个整数数组 nums，将它重新排列成 nums[0] nums[2] < nums[3]... 的顺序。 你可以假设所有输入数组都可以得到满足题目要求的结果。

📖 文章摘要

本文详细解析LeetCode第324题“摆动排序 II”，这是一道数组排序的中等难度问题。文章提供了排序+双指针和O(n)时间复杂度的解法，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能对比。适合想要提升数组操作和排序算法能力的程序员。

核心知识点： 排序、双指针、虚拟索引
难度等级： 中等
推荐人群： 具有基础算法知识，想要提升数组操作能力的程序员

题目描述

给你一个整数数组 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 ，总能产生满足题目要求的结果

解题思路

方法一：排序 + 双指针

这种方法先对数组排序，然后将较小的一半和较大的一半交错放置。

关键点：

  • 先将数组排序
  • 从中间分成两部分
  • 从后向前填充，避免相等元素相邻
  • 处理奇偶长度的情况

具体步骤：

  1. 对数组进行排序
  2. 找到数组中点
  3. 从两部分的末尾开始交错填充新数组
  4. 将结果复制回原数组

时间复杂度：O(nlogn) 空间复杂度：O(n)

方法二：O(n)时间复杂度解法

使用快速选择找到中位数，然后使用三向切分的思想重排数组。

关键点：

  • 使用快速选择找到中位数
  • 使用虚拟索引映射
  • 三向切分处理相等元素
  • 原地重排数组

具体步骤：

  1. 找到数组的中位数
  2. 使用虚拟索引重排数组
  3. 处理相等的元素
  4. 完成最终排序

时间复杂度：O(n) 空间复杂度：O(1)

图解思路

排序+双指针过程分析表

步骤 原数组 排序后 结果数组 说明
初始 [1,5,1,1,6,4] [1,1,1,4,5,6] [] 排序完成
1 - - [1,6] 填充第1对
2 - - [1,6,1,5] 填充第2对
3 - - [1,6,1,5,1,4] 填充第3对

虚拟索引映射表

原始索引 0 1 2 3 4 5
映射索引 1 3 5 0 2 4
元素 1 6 1 5 1 4

代码实现

C# 实现

public class Solution {
    public void WiggleSort(int[] nums) {
        int n = nums.Length;
        int[] temp = new int[n];
        Array.Copy(nums, temp, n);
        Array.Sort(temp);
        
        int mid = (n - 1) / 2;
        int right = n - 1;
        
        // 从后向前填充，避免相等元素相邻
        for (int i = 0; i < n; i++) {
            nums[i] = i % 2 == 0 ? temp[mid--] : temp[right--];
        }
    }
}

Python 实现

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

C++ 实现

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

执行结果

C# 实现

  • 执行用时：160 ms
  • 内存消耗：46.8 MB

Python 实现

  • 执行用时：172 ms
  • 内存消耗：17.2 MB

C++ 实现

  • 执行用时：16 ms
  • 内存消耗：17.6 MB

性能对比

语言 执行用时 内存消耗 特点
C# 160 ms 46.8 MB 实现简洁，性能适中
Python 172 ms 17.2 MB 代码最简洁
C++ 16 ms 17.6 MB 性能最优

代码亮点

  1. 🎯 巧妙利用奇偶索引分配元素
  2. 💡 从后向前填充避免相等元素相邻
  3. 🔍 使用临时数组保证稳定性
  4. 🎨 代码结构清晰，易于理解

常见错误分析

  1. 🚫 没有考虑相等元素的情况
  2. 🚫 数组分割点计算错误
  3. 🚫 填充顺序导致相等元素相邻
  4. 🚫 没有正确处理边界情况

解法对比

解法 时间复杂度 空间复杂度 优点 缺点
排序+双指针 O(nlogn) O(n) 实现简单，稳定 空间复杂度高
三向切分 O(n) O(1) 时空复杂度优 实现复杂

相关题目

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新至第324题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

  • 👍 点个赞，让更多人看到这篇文章
  • 📁 收藏文章，方便后续查阅复习
  • 🔔 关注作者，获取更多高质量算法题解
  • 💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！