# 324 Wiggle Sort II

## 324. [Wiggle Sort II](https://leetcode.com/problems/wiggle-sort-ii/description/)

## 1. Question

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

**Example:**\
(1) Given`nums = [1, 5, 1, 1, 6, 4]`, one possible answer is`[1, 4, 1, 5, 1, 6]`.\
(2) Given`nums = [1, 3, 2, 2, 3, 1]`, one possible answer is`[2, 3, 1, 3, 1, 2]`.

**Note:**\
You may assume all input has valid answer.

**Follow Up:**

## 2. Implementation

**(1) Sort**&#x20;

```java
class Solution {
    public void wiggleSort(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }

        Arrays.sort(nums);
        int n = nums.length;
        int[] temp = new int[n];

        int low = (n + 1) / 2, high = n;

        for (int i = 0; i < n; i++) {
            temp[i] = i % 2 == 0 ? nums[--low] : nums[--high];
        }

        for (int i = 0; i < n; i++) {
            nums[i] = temp[i];
        }
    }
}
```

**(2) Quick Select**

```java
class Solution {
    public void wiggleSort(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }

        int n = nums.length;
        int median = getKthNum(nums, 0, n - 1, n/2);

        int[] temp = new int[n];
        int start = 0, end = n - 1;

        for (int num : nums) {
            if (num < median) {
                temp[start++] = num;
            }
            else if (num > median) {
                temp[end--] = num;
            }
        }

        for (int i = start; i <= end; i++) {
            temp[i] = median;
        }

        int low = (n + 1) / 2, high = n;

        for (int i = 0; i < n; i++) {
            nums[i] = (i % 2 == 0) ? temp[--low] : temp[--high];
        }
    }

    public int getKthNum(int[] nums, int start, int end, int k) {
        int pivot = partition(nums, start, end);

        if (pivot < k) {
            return getKthNum(nums, pivot + 1, end, k);
        }
        else if (pivot > k) {
            return getKthNum(nums, start, pivot - 1, k);
        }
        else {
            return nums[pivot];
        }
    }

    public int partition(int[] nums, int start, int end) {
        int mid = start + (end - start) / 2;

        swap(nums, mid, end);

        for (int i = start; i < end; i++) {
            if (nums[i] < nums[end]) {
                swap(nums, start, i);
                ++start;
            }
        }

        swap(nums, start, end);
        return start;
    }

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

## 3. Time & Space Complexity

**Sort :** 时间复杂度O(nlogn), 空间复杂度O(n)

**Quick Select**: 时间复杂度O(n), 空间复杂度O(n)