[LeetCode] Problem 324 - Wiggle Sort II

Posted on | In ,

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

Example

No.1

Input: nums = [1, 5, 1, 1, 6, 4]

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

No.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?

O(nlogn) runtime, O(n) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void wiggleSort(int[] nums) {
    int[] copy = nums.clone();
    Arrays.sort(copy);
    int left = (copy.length - 1) >> 1;
    int right = copy.length - 1;
    int idx = 0;

    while (left >= 0 && right >= (copy.length + 1) >> 1) {
        nums[idx++] = copy[left--];
        nums[idx++] = copy[right--];
    }

    if (left == 0)
        nums[idx] = copy[0];
}

O(n) runtime, O(1) 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
public void wiggleSort(int[] nums) {
    int n = nums.length;
    int lo = 0;
    int hi = n - 1;
    int midNum = partition(nums, lo, hi, (n - 1) >> 1);

    for (int i = 0; i <= hi;) {
        if (nums[getMapIdx(i, n)] > midNum)
            swap(nums, getMapIdx(i++, n) , getMapIdx(lo++, n));
        else if (nums[getMapIdx(i, n)] < midNum)
            swap(nums, getMapIdx(i, n), getMapIdx(hi--, n));
        else
            i++;
    }
}

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

private int getMapIdx(int i, int n) {
    return (2 * i + 1) % (n | 1);
}

private int partition(int[] nums, int lo, int hi, int k) {
    int left = lo;
    int right = hi;
    int num = nums[lo];

    while (left < right) {
        while (left < right && nums[right] >= num)
            right--;

        while (left < right && nums[left] <= num)
            left++;

        swap(nums, left, right);
    }
    
    swap(nums, lo, left);

    if (left - lo == k)
        return num;
    else if (left - lo < k)
        return partition(nums, left + 1, hi, k - (left - lo + 1));
    else
        return partition(nums, lo, right - 1, k);
}