每日一道算法：leetcode 刷题碰到的问题。

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: Can you do it in O(n) time and/or in-place with O(1) extraspace?

我的思路比较简单虽然通过了但是用了1081ms所以其实无论是时间复杂度还是空间复杂度都达不到要求，希望各位谁感兴趣的话试着用C做一下。下面是我的代码，如果有大神能帮我想到改进的方法也可以啊。（大体上是先快排之后然后再把后面一半的数插入前面一半的数）：

void quicksort(int *nums, int numsSize);
void wiggleSort(int *nums, int numsSize){
    quicksort(nums, numsSize);
    int counter = 0;
    int left = (numsSize - 1) / 2;
    int right = numsSize - 1; 
    int cache[numsSize];
    
    for(counter=1; counter <= numsSize; counter++){
        if((counter & 1) == 1){
            cache[counter - 1] = nums[left--];
        }
        else{
            cache[counter - 1] = nums[right--];
        }
    }
    for(counter=0; counter<numsSize; counter++){
        nums[counter] = cache[counter];
    }
}

void quicksort(int *nums, int numsSize){
    if(numsSize <= 1){
        return;
    }
    int left = 0;
    int right = numsSize - 1;
    int key = nums[left];

    while(left < right){
        while(nums[right] >= key && left < right){
            right--;
        } 
        nums[left] = nums[right];
        while(left < right && nums[left] <= key){
            left++;
        }
        nums[right] = nums[left];
    }
    nums[left] = key;

    quicksort(nums, left);
    quicksort(nums+left+1, numsSize - 1 - left);

}

另外在网上看到有些人的思路是先找出中指点（据说只需要O（n）的时间复杂度，我不知道为什么只要O（n）的时间复杂度就能找到中指点，希望有知道的大神顺便也帮我解释一下）。

Answer 1

排序和插入每个都很耗时，所以你的方法是非常低效的。我说一下我的思路。

首先，题目说了给的输入是肯定有解的，所以就不需要考虑无解的情况了。由这一前提，我们可以遍历数组，交换数组中适当的项来达到目的。具体步骤为：

1. 初始化2个索引：n1=0,n2=1

2. 用这两个索引由前至后遍历数组，判断当前元素是否满足规则（即元素按照大于和小于的顺序交替出现）

3. 当不满足规则时，分情况讨论：

(1) 需要较大的元素，但目标元素却比当前元素小。此时只需交换两个元素的位置即可
(2) 需要较小的元素，但目标元素却比当前元素大。此时也只需交换两个元素的位置即可
(3) 目标元素与当前元素相等。此时需要从n2+1开始查找，尝试找到一个不相等的元素。此时又分2种情况：

(3.1) 顺利找到了一个元素，将其与n2处的元素交换，然后按照(1)或(2)的规则决定是否交换n1,n2两个元素
(3.2) 没有找到符合条件的元素。换句话说，此时n1、n2及其后面的元素的值都是相等的。这时候我们需要把n2及其后面的元素插入到前面的元素中去，插入规则为：

(3.2.1) 两个相邻元素是降序，那么只要：(a) 待插入元素比它们都小时，可以在它们中间和后面各插入一个，插入后仍然满足规则；(b) 待插入元素比它们都大时，可以在它们前面和中间各插入一个，插入后仍然满足规则。例如将1插入4,2的中间和后面之后变为4,1,2,1，关系由4>2变为了4>1<2>1，仍然满足规则。
(3.2.2) 同理，两个相邻元素是升序时。(a) 待插入元素比它们都小时，可以在它们前面和中间各插入一个，插入后仍然满足规则；(b) 待插入元素比它们都大时，可以在它们中间和后面各插入一个，插入后仍然满足规则。

---

注意：

1. 插入必须是成对的，因此，如果最后的元素个数为奇数时，n1处的元素不需要动，只需交换n2及其后面的偶数个元素即可。反之，如果最后的元素个数为偶数，那么n1处的元素也需要参与交换。

2. 这种方法是否一定能找到一个解？答案是肯定的，因为最后的m个相同的数的数量必然不大于全部元素个数的一半，否则原本就是无解的。即使最坏的情况，我们也能找到足够多的位置插入这些元素。

该算法时间复杂度接近O(n)（理想情况只需遍历一遍，最坏情况需要插入n/2个元素，每次插入都需要移动一部分数组元素），空间复杂度O(1)（除几个索引之外不需要额外存储空间）

---

更新：

刚才又仔细思考了一下，发现根本不需要插入操作，只需要交换即可。上面的整个(3.2)步骤可以修改为：

(3.2) 没有找到符合条件的元素。换句话说，此时n1、n2及其后面的元素的值都是相等的。此时依次遍历n2及其之后的元素（n1不用动），并按以下规则与前面的元素进行交换：

(3.2.1) 当前位置需要一个较大的元素，则在前面查找出2个比该元素都大的元素，然后将较小的元素与当前元素交换，交换后原来元素仍然满足规则，当前位置前后也将满足规则
(3.2.2) 同理，当前位置需要一个较小的元素，则在前面查找出2个比该元素都小的元素，然后将较大的元素与当前元素交换，交换后原来元素仍然满足规则，当前位置前后也将满足规则
(3.2.3)成功交换后，当前索引向后移动2个元素，然后进行下一轮交换