# Wiggle Sort I & II

* **Wiggle sort 类问题**
  * **如何利用单调性**
  * **怎么 partition**
  * **什么顺序穿插**
  * **如何 in-place**

#### 下面这两题 googe 都很喜欢。

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

首先这题一看就是要你 O(n) 解的，而且要 in-place，不然毫无挑战，因为 quick sort 都 O(n log n)

这题在条件上，比 Wiggle Sort II 要宽松，因此代码变的可以很简单。

* **wiggle sort 依然利用的数组的单调性，只不过这个单调性每走一步会变一次方向；**
* **如果两对相邻元素有同样的单调性，就不符合题意要求。但是在这种情况下，交换后一对元素的位置，就一定可以得到正确结果。**
* [**这题还有一个google面经题变种，在这个帖子中，思想非常类似，更利于思考 wiggle sort 的本质**](http://www.1point3acres.com/bbs/thread-146255-1-1.html)

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

        boolean findBigger = true;
        for(int i = 1; i < nums.length; i++){
            if(findBigger){
                if(nums[i] < nums[i - 1]){
                    swap(nums, i, i - 1);
                }
            } else {
                if(nums[i] > nums[i - 1]){
                    swap(nums, i, i - 1);
                }
            }
            findBigger = !findBigger;
        }
    }

    private void swap(int[] nums, int a, int b){
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}
```

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

在 Wiggle Sort I 的基础上拿掉了等于号条件，整个题都 gay 了好多，因为这次如果相邻两个数是相等的，怎么 swap 都不符合题意。如果单纯的按顺序扫，就不可避免的会遇到到“找正确元素”的步骤，这个步骤一旦多了，复杂度就上去了。

先写个时间空间都各种不正确的写法，感受下思路。从后往前依次找剩余元素中最大的，按正序插入数组。

有的 test case 是【4,5,5,6】，属于"有重复元素" && "重复元素在第二次遍历插入" && "正好和前一轮结尾相邻" 的情况，所以都正序插入会出 bug.

```java
public class Solution {
    public void wiggleSort(int[] nums) {
        if(nums == null || nums.length < 2) return;
        Arrays.sort(nums);
        int[] ans = new int[nums.length];
        int index = nums.length - 1;

        for(int i = 1; i < nums.length; index--){
            ans[i] = nums[index];
            i += 2;
        }

        for(int i = 0; i < nums.length; index--){
            ans[i] = nums[index];
            i += 2;
        }

        for(int i = 0; i < nums.length; i++){
            nums[i] = ans[i];
        }
    }
}
```

#### 关于这题，[这个帖子](https://leetcode.com/discuss/95156/step-by-step-explanation-of-index-mapping-in-java)写的非常详尽，里面用到了 [virtual indexing](https://leetcode.com/discuss/77133/o-n-o-1-after-median-virtual-indexing) 的思想

### A(i) = nums\[(1+2\*(i)) % (n|1)]

(n|1) 强行变奇数。

![](/files/-MUt7aNOONh21T_imxGt)

上面那个 sort 之后从大到小正序穿插插入的顺序，和这题一样，不同之处是，这个写法更符合题目的本质：不需要排序，只需要 partitioning. 正确 partition 的数组只要按照这个顺序插入，都是正确的。

* **于是问题就分成了三个子问题：**
  * **怎么 partitioning**
  * **什么顺序穿插**
  * **如何 in-place**

```java
   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);
    }
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mnunknown.gitbook.io/algorithm-notes/two_pointers/614-_two_pointers-_shuang_zhi_zhen.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.