> For the complete documentation index, see [llms.txt](https://mnunknown.gitbook.io/algorithm-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mnunknown.gitbook.io/algorithm-notes/two_pointers/614-_two_pointers-_shuang_zhi_zhen.md).

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