LeetCode 324. 摆动排序 II

Categories:

题目描述
思路分析
1. 解法一：排序 + 交错填充（推荐）
相似题目

题目描述

✅ 324. 摆动排序 II

思路分析

解法一：排序 + 交错填充（推荐）

核心思路：

先对数组排序，取较小一半与较大一半。

将较小一半从大到小填入偶数位，将较大一半从大到小填入奇数位。

通过交错填充保证摆动关系成立，且能处理重复元素。

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示数组长度。

空间复杂度：O(n)，用于临时数组。

import java.util.Arrays;

class Solution {
    public void wiggleSort(int[] nums) {
        int n = nums.length;
        int[] sorted = nums.clone();
        Arrays.sort(sorted);

        int left = (n - 1) / 2;
        int right = n - 1;

        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                res[i] = sorted[left--];
            } else {
                res[i] = sorted[right--];
            }
        }

        System.arraycopy(res, 0, nums, 0, n);
    }
}

import "sort"

func wiggleSort(nums []int) {
	n := len(nums)
	sorted := make([]int, n)
	copy(sorted, nums)
	sort.Ints(sorted)

	left := (n - 1) / 2
	right := n - 1

	res := make([]int, n)
	for i := 0; i < n; i++ {
		if i%2 == 0 {
			res[i] = sorted[left]
			left--
		} else {
			res[i] = sorted[right]
			right--
		}
	}

	copy(nums, res)
}

相似题目

题目	难度	考察点
280. 摆动排序	中等	贪心
376. 摆动序列	中等	贪心
215. 数组中的第K个最大元素	中等	快速选择
75. 颜色分类	中等	双指针
912. 排序数组	中等	排序

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/79011803