leetcode 324. Wiggle Sort II

没想到这道题做了那么久啊，AC了真是神清气爽，又复习了一次快排。

思路是，首先将数组用quickSelect部分排序，以median为界限，然后

还是用三值排序的思路，得保证比median小的数都尽量排到从左到右的奇数位置，

比median大的数都尽量排到从右到左的偶数位置，剩下的median自然就分好了位置。

大致思路是这样，不过好多细节，提交了无数个版本，每次都有bad case，真是心好累。

一开始还把quickSelect写错了，到后面才发现。quickSelecthttps://en.wikipedia.org/wiki/Quickselect

先记录下AC版本的吧，太不容易了。

class Solution {public:    void wiggleSort(vector<int>& nums) {        //quickSelect        int vecSize = int(nums.size());        int leftInd = 0, rightInd = vecSize - 1, pivotInd = 0, temp = 0;        while (leftInd <= rightInd) {            pivotInd = leftInd + (rightInd - leftInd) / 2;            temp = nums[pivotInd];            nums[pivotInd] = nums[rightInd];            nums[rightInd] = temp;            int i = 0, j = rightInd - 1;            while (i <= j) {                if (nums[i] > nums[rightInd]) {                    temp = nums[i];                    nums[i] = nums[j];                    nums[j] = temp;                    j--;                } else {                    i++;                }            }            temp = nums[i];            nums[i] = nums[rightInd];            nums[rightInd] = temp;            if (i == (vecSize - 1) / 2) {                break;            } else if (i < vecSize / 2) {                leftInd = i + 1;            } else {                rightInd = i - 1;            }        }        /*         还是用三值排序的思路，得保证比median小的数都尽量排到从左到右的奇数位置，         比median大的数都尽量排到从右到左的偶数位置，剩下的median自然就分好了位置。         */        int lessInd = 0, iterInd = 0, largeInd = vecSize - 1, median = nums[pivotInd];        while (iterInd <= largeInd) {            int iterMapInd = getMapInd(iterInd, vecSize);            if (nums[iterMapInd] < median) {                int lessMapInd = getMapInd(lessInd, vecSize);                int temp = nums[iterMapInd];                nums[iterMapInd] = nums[lessMapInd];                nums[lessMapInd] = temp;                iterInd++;                lessInd++;            } else if (nums[iterMapInd] > median) {                int largeMapInd = getMapInd(largeInd, vecSize);                int temp = nums[iterMapInd];                nums[iterMapInd] = nums[largeMapInd];                nums[largeMapInd] = temp;                largeInd--;            } else {                iterInd++;            }        }    }PRivate:    int getMapInd(int ind, int vecSize) {        if (ind >= (vecSize + 1) / 2) {            return 2 * vecSize - 1- 2 * ind;        } else {            return vecSize % 2 == 0? vecSize - 2 - 2 * ind : vecSize - 1 - 2 * ind;        }    }};
接下来是一直WA的心路历程。。。
一直在想，为什么参考大家的解答，排列的顺序都是：
         Index :       0   1   2   3   4   5
         Small half:   M       S       S
         Large half:       L       L       M
而我自己觉得
         Index :       0   1   2   3   4   5
         Small half:   S       S       M
         Large half:       M       L       L
这种排序也可以啊，直到遇到一个bad case：{4,5,5,6}才发现当S的个数<=1的时候上面这种排序还是成立的，而我的这种排序就gg了，心酸。
         Index :       0   1   2   3   4   5
         Small half:   M       S
         Large half:       L       M
         
         Index :       0   1   2   3   4   5
         Small half:   S       M
         Large half:       M       L
好吧，所以索引公式int mapInd = startInd > pivotInd ? 2 * (startInd - pivotInd - 1) + 1 : 2 * startInd;又得改了。
正确的索引顺序是，大于median的数从左到右，放在奇数的位置，小于median的数从右到左放在偶数的位置，找一下索引的对应关系。找出了对应关系：
         当size是偶数时：
            大于median的数（右半部分，从右到左）mapInd = 2 * size - 1 - 2 * ind (ind = [(size + 1) / 2, size - 1])
            小于median的数（左半部分，从左到右）mapInd = size - 2 - 2 * ind (ind = [0, (size - 1) / 2])
         当size是奇数时：
            大于median的数（右半部分）mapInd = 2 * size - 1 - 2 * ind (ind = [(size + 1) / 2, size - 1])
            小于median的数（左半部分，从左到右）mapInd = size - 1 - 2 * ind (ind = [0, (size - 1) / 2])
这块写的是啥，真是没脸看了。。。就当记录一下自己的脑残
int startInd = 1, temp = vecSize > 0 ? nums[1] : 0, judgeInd = 1;        while (startInd < vecSize) {            int mapInd = startInd > pivotInd ? 2 * (startInd - pivotInd - 1) + 1 : 2 * startInd;            while (judgeInd != mapInd) {                temp = nums[startInd];                nums[startInd] = nums[mapInd];                nums[mapInd] = temp;                startInd = mapInd;                mapInd = startInd > pivotInd ? 2 * (startInd - pivotInd - 1) + 1 : 2 * startInd;            }            startInd++;            judgeInd = startInd;        }一开始还写了一个超简易的交换思路，后来查了一下，如果数组里面没有重复元素的话还是OK的，但是这里就用不了了。
这样交换位置的方法会遇到bad case：1,1,2,2,3,3
int endInd = vecSize - 1;        int startInd = (vecSize % 2) == 1 ? 1 : 0;        while (startInd <= endInd) {            if (startInd % 2 == 1) {                int temp = nums[startInd];                nums[startInd] = nums[endInd];                nums[endInd] = temp;            }            startInd++;            endInd--;        }