【LeetCode】324. Wiggle Sort II 摆动排序 II（Medium）（JAVA）

题目地址: https://leetcode.com/problems/wiggle-sort-ii/

题目描述：

Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]…

Example 1:

Input: nums = [1, 5, 1, 1, 6, 4]
Output: One possible answer is [1, 4, 1, 5, 1, 6].

Example 2:

Input: nums = [1, 3, 2, 2, 3, 1]
Output: One possible answer is [2, 3, 1, 3, 1, 2].

Note:
You may assume all input has valid answer.

Follow Up:
Can you do it in O(n) time and/or in-place with O(1) extra space?

题目大意

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

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

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

解题方法

1. 对数组进行排序，然后把数字进行穿插
2. [0, 1, 2, 3, 4, 5, 6] --> 1 <-> 6 交换, 3 <-> 4 交换, [0, 6, 2, 4, 3, 5, 1], 也就是最小的奇数位和最大的偶数位从头到尾进行交换 （因为左边的偶数位已经比较小了，右边的奇数位已经比较大了，不需要改动，只需要改动左边的奇数和右边的偶数即可，也就是这两个交换）
3. note: 比如 [1,1,2,2,2,3] 交换后的结果为: [1,2,2,2,1,3] 不满足要求，所以还需要进行一定的交换，遇到 nums[i] == nums[i + 1] 的，i 在奇数位就和奇数的最大值进行交换，如果是偶数位就和偶数位的最小值进行交换
   （之所以这样交换，是因为 nums[i] == nums[i + 1] 肯定是中间的值，上述交换后，能把中间值往两边移）
4. note: 如果不考虑 in-place 的要求，可以把数组分为： [1,1,2], [2,2,3] 然后分别逆转，[2,1,1], [3,2,2] 再进行穿插即可 （这样做的目的是，让重复的中间值在第一个出现，就可以让重复的值出现的尽可能多，而且两个数组的中间值需要进行远离，才进行了两个分别逆转）

class Solution {
    public void wiggleSort(int[] nums) {
        Arrays.sort(nums);
        int end = nums.length % 2 == 0 ? nums.length - 2 : nums.length - 1;
        for (int i = 1; i < end; i += 2, end -=2) {
            swap(nums, i, end);
        }
        int start = 0;
        end = nums.length % 2 == 0 ? nums.length - 1 : nums.length - 2;
        for (int i = 0; i < nums.length - 1; i ++) {
            if (nums[i] != nums[i + 1]) continue;
            if (i % 2 == 1) {
                swap(nums, i, end);
                end -= 2;
            } else {
                swap(nums, i, start);
                start += 2;
            }
        }
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

执行耗时:4 ms,击败了84.24% 的Java用户
内存消耗:42.1 MB,击败了17.70% 的Java用户

欢迎关注我的公众号，LeetCode 每日一题更新