dustfree's blog
0%

Wiggle Sort II

Posted on In ,

Question

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].

Solution

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
/*
@param: int[] nums
@return: void
Algorithm: 是一道组合题目，正常思路是将其从大到小排序，例一 [6,5,4,1,1,1]
[6,5,4,1,1,1]
将 6，5，4放到index为1，3，5位置上；1，1，1放到index为0，2，4的位置上
[1,6,1,5,1,4]

即求出nums的中位数，这里用到https://leetcode.com/problems/kth-largest-element-in-an-array/ 的解法
然后将其partition，再按照"color sort"的思路解题
*/
public void wiggleSort(int[] nums) {
    int median = findKthLargest(nums, (nums.length + 1) / 2);
    int n = nums.length;

    int left = 0, i = 0, right = n - 1;

    while (i <= right) {

        if (nums[newIndex(i,n)] > median) {
            swap(nums, newIndex(left++,n), newIndex(i++,n));
        }
        else if (nums[newIndex(i,n)] < median) {
            swap(nums, newIndex(right--,n), newIndex(i,n));
        }
        else {
            i++;
        }
    }
}

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

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

public int findKthLargest(int[] nums, int k) {
    if (nums == null || nums.length == 0) {
        return -1;
    }
    if (k <= 0 || k > nums.length) {
        return -1;
    }
    
    return partition(nums, 0, nums.length-1, k-1);
}

public int partition(int[] nums, int start, int end, int k) {
    if (start >= end) {
        return nums[k];
    }
    
    int left = start, right = end;
    int pivot = nums[start+(end-start)/2];
    
    while (left <= right) {
        while (left <= right && nums[left] > pivot) {
            left++;
        }
        
        while (left <= right && nums[right] < pivot) {
            right--;
        }
        if (left <= right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }
    
    if (k <= right) {
        return partition(nums, start, right, k);
    }
    if (k >= left) {
        return partition(nums, left, end, k);
    }
    return nums[k];
}