1.题目描述
给你一个整数数组 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]
2.解题思路与代码
2.1 解题思路
这道题需要将原数组排列成 nums[0] < nums[1] > nums[2] < nums[3] 这样一大一小的结构，那么我们可以将数组进行按照从小到大排序，并从中间切分，左边部分是较小的，右边部分是较大，然后按照一小一大的顺序依次放回数组，便能够得到结果。以数组 nums = [1,5,1,1,6,4] 为例
使用 left 指向较小部分最右侧，right 指向较大部分左右侧，用 getSmaller 来决定是选择较小部分还是较大部分的数
2.2 代码
class Solution {
public void wiggleSort(int[] nums) {
// 使用一个临时数组暂存
int[] tmp = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
tmp[i] = nums[i];
}
// 对数组进行排序
Arrays.sort(tmp);
// left 从较小区域的最右侧开始
int left = (nums.length - 1) >> 1;
// right 从较大区域的最右侧开始
int right = nums.length - 1;
// 是否选择较小区域
boolean getSmaller = true;
for (int i = 0; i < nums.length; i++) {
if (getSmaller) {
// 选择较小区域，left 左移一位，并 getSmaller 变为false 下次取较大区域
nums[i] = tmp[left--];
getSmaller = false;
} else {
// 选择较大区域，right 左移一位，并 getSmaller 变为true 下次取较小区域
nums[i] = tmp[right--];
getSmaller = true;
}
}
}
}
2.3 测试结果
通过测试
测试结果
3.总结
- 首先对数组进行排序，然后对半分成较小数区域和较大数区域
- 使用双指针来对较小区域和较大区域进行选择并放入数组中
