当前位置：首页 > news >正文

LeetCode题练习与总结：摆动排序 Ⅱ--324

news 2024/10/22 13:57:37

一、题目描述

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

二、解题思路

首先对数组进行排序。
然后将排序后的数组分成两部分，前半部分和后半部分。
将前半部分的元素按照从大到小的顺序填充到结果的偶数索引位置。
将后半部分的元素按照从小到大的顺序填充到结果的奇数索引位置。

这样，我们可以确保 nums[0] < nums[1] > nums[2] < nums[3]… 的顺序。

三、具体代码

import java.util.Arrays;class Solution {public void wiggleSort(int[] nums) {// 对数组进行排序Arrays.sort(nums);// 创建一个新数组，用于存放结果int[] temp = new int[nums.length];// 填充新数组的偶数索引位置int left = (nums.length - 1) / 2; // 前半部分的最后一个索引int right = nums.length - 1; // 后半部分的最后一个索引int index = 0;while (left >= 0) {temp[index] = nums[left];left--;index += 2;}// 填充新数组的奇数索引位置index = 1;while (right > (nums.length - 1) / 2) {temp[index] = nums[right];right--;index += 2;}// 将结果复制回原数组System.arraycopy(temp, 0, nums, 0, nums.length);}
}

四、时间复杂度和空间复杂度

1. 时间复杂度

排序操作：Arrays.sort(nums); 的时间复杂度为 O(n log n)，其中 n 是数组 nums 的长度。
填充新数组 temp 的偶数索引位置：这个循环会遍历原数组的一半元素，所以时间复杂度为 O(n/2)，即 O(n)。
填充新数组 temp 的奇数索引位置：这个循环也会遍历原数组的一半元素，所以时间复杂度同样为 O(n/2)，即 O(n)。
将结果复制回原数组：System.arraycopy(temp, 0, nums, 0, nums.length); 的时间复杂度为 O(n)。

将上述步骤的时间复杂度相加，总的时间复杂度由排序操作决定，因此总的时间复杂度为 O(n log n)。

2. 空间复杂度

新数组 temp 的大小与原数组 nums 相同，所以空间复杂度为 O(n)。

五、总结知识点

数组排序：
- 使用 Arrays.sort() 方法对数组进行排序。这是 Java 标准库中的一个方法，它使用双轴快速排序算法（Dual-Pivot Quicksort）对数组进行排序。
数组操作：
- 创建新数组 temp 来存储重新排列后的数组元素，这是因为 Java 中的数组是不可变的（即大小固定），无法直接在原数组上进行“就地”重新排列。
循环结构：
- 使用 while 循环来遍历数组的一半元素，并将它们按照题目要求放置到新数组的偶数索引位置和奇数索引位置。
索引操作：
- 使用索引变量 left 和 right 分别指向排序后数组的前半部分和后半部分的最后一个元素。
- 使用索引变量 index 来确定新数组 temp 中元素的放置位置。
数组复制：
- 使用 System.arraycopy() 方法将新数组 temp 中的元素复制回原数组 nums。这是一个高效的数组复制方法，它在内部使用系统级别的复制操作。
算术运算：
- 计算数组中间位置索引 (nums.length - 1) / 2，以确定数组前半部分和后半部分的分界点。
逻辑判断：
- 在 while 循环中使用条件判断来确定循环何时结束，即当索引 left 或 right 达到特定的边界值时。
变量递减：
- 在循环体内，通过递减操作（left-- 和 right--）来移动索引，确保遍历数组时不会重复访问元素。