LeetCode: 324. Wiggle Sort II

友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

支付宝

有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

324. Wiggle Sort II

LeetCode - 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?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Runtime: 3 ms, faster than 99.88% of Java online submissions for Wiggle Sort II.
 *
 * Memory Usage: 44.2 MB, less than 10.00% of Java online submissions for Wiggle Sort II.
 *
 * Copy from https://leetcode-cn.com/problems/wiggle-sort-ii/solution/javaxiang-xi-ti-jie-shuo-ming-by-heator/[Java详细题解说明 - 摆动排序 II - 力扣（LeetCode）]
 */
public void wiggleSort(int[] nums) {
    Arrays.sort(nums);
    int length = nums.length;
    int[] smaller = new int[length % 2 == 0 ? length / 2 : (length / 2 + 1)];
    int[] bigger = new int[length / 2];
    System.arraycopy(nums, 0, smaller, 0, smaller.length);
    System.arraycopy(nums, smaller.length, bigger, 0, bigger.length);
    int i = 0;
    for (; i < length / 2; i++) {
        int si = smaller.length - 1 - i;
        nums[2 * i] = smaller[si];
        int bi = length / 2 - 1 - i;
        nums[2 * i + 1] = bigger[bi];
    }
    if (length % 2 != 0) {
        nums[2 * i] = smaller[smaller.length - 1 - i];
    }
}