LEETCODE 324. Wiggle Sort II 解题思路分析

题目大意：

摆动排序 II

给定一个无序的数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]... 的顺序。

示例 1:

输入: nums = [1, 5, 1, 1, 6, 4]
输出: 一个可能的答案是 [1, 4, 1, 5, 1, 6]

示例 2:

输入: nums = [1, 3, 2, 2, 3, 1]
输出: 一个可能的答案是 [2, 3, 1, 3, 1, 2]

说明:
你可以假设所有输入都会得到有效的结果。

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

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=324

解题思路分析：

题目要求按照一小一大，一小一大的顺序排序数组。最简单的想法是我们先将整个数组按照从小到大的顺序排列，然后从数组中间将数组分成两部分，保证左边半个数组中的最大元素小于等于右边半个数组中的最小元素，这时，我们按照顺序分别从左边和右边各取一个数字，这样就能保证一小一大的排序。

另外需要注意一点，取数字时要从大到小的取，否则可能会出现某两个连续数字相同的情况。比如[1,2,2,3],我们将数组分为[1,2]和[2,3]左右两个部分，如果从大到小取，左边先取2，右边先取3，然后左边再取1，右边再取2，会得到正确答案[2,3,1,2],反之如果从小到大取的话，会得到[1,2,2,3]。

实现代码：

public void wiggleSort(int[] nums) {
    Arrays.sort(nums); // 排序数组
    // copy一份新的数组
    int[] temp = Arrays.copyOf(nums, nums.length);
    // 将数组分成两部分，右边数组最大index为nums.length-1
    int bigIndex=nums.length-1;
    // 左边数组最大index为数组的一半
    int samllIndex=nums.length/2;
    // 当整个数组个数为偶数时，为了保证左右两边个数相同，左数组最大idnex减一
    if(nums.length%2==0) samllIndex--;
    // 从两边数组的各取一个最大值
    for(int i=0;i<nums.length/2;i++){
        nums[i*2]=temp[samllIndex--];
        nums[i*2+1]=temp[bigIndex--];
    }
    // 如果数组个数为奇数，将左数组剩余的那个数放到愿数组最尾处。
    if(nums.length%2==1) {
        nums[nums.length-1]=temp[0];
    }
}

本题解法执行时间为4ms。

Runtime: 4 ms, faster than 48.96% of Java online submissions for Wiggle Sort II.

Memory Usage: 51 MB, less than 10.00% of Java online submissions for Wiggle Sort II.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-324-wiggle-sort-ii-解题思路分析/