Wiggle Sort II

原題鏈接Wiggle Sort II

給定一個序列，要求將其按大于小于交替的方式排列，即nums[0] < nums[1] > nums[2] < nums[3]…

對于序列中的元素，假設中位數為median，那么元素能夠被分成三類

• 大于median
• 小于median
• 等于median

對于中位數，可以使用stl中的nth_element算法求得，即

int n = nums.size(); auto middle = nums.begin() + n / 2; std::nth_element(nums.begin(), middle, nums.end()); int median = *middle;

nth_element算法返回后，

• middle左邊的元素都小于等于median，但不一定是有序的
• middle右邊的元素都大于等于median，同樣不一定是有序的

注意，左右兩邊都可能有等于median的元素存在

另外，可能給這三類元素安排適當的位置以滿足題目要求

• 將大于median的元素放在前幾個奇數位置上（位置從0開始）
• 將小于median的元素放在后幾個偶數位置上
• 不改變等于median的元素位置

所以，需要

• 一個變量i記錄大于median的元素應該放到的位置，這個位置應該始終是奇數位置
• 一個變量k記錄小于median的元素應該放到的位置，這個位置應該始終是偶數位置
• 一個變量j記錄當前遍歷到的元素

所以

• i指向的位置一定是下一個奇數位置，如果j指向的元素大于median，那么就將其和i指向的元素交換
• k指向的位置一定是下一個偶數位置，如果j指向的元素小于median，那么就將其和k指向的元素交換
• 如果j指向的元素等于median，那么暫時不知道應該將它放在哪，所以就先不管它，繼續遍歷下一個元素，因為遲早i或k會指向這個位置并且和一個符合大小關系的元素交換

---

通過上面的過程，可以發現與median相等的元素會被推來推去，自始至終不知道應該放在哪，直到最后遍歷結束，它停在哪就是哪。

但是，這樣會不會有兩個值為median的元素挨在一起，也就是說奇數位置上的值是median，同時與他相鄰的某個偶數位置上的值也是median導致排序失敗

為了避免這個問題，可以采用一種方法，即另j每次移動兩步，也就是說先另j直線奇數位置，再另j指向偶數位置，所以對于大小為10的序列，j的變化可能像是這樣

1 -> 3 -> 5 -> 7 -> 9 -> 0 -> 2 -> 4 -> 6 -> 8

暫且先不考慮怎么實現這樣的改變，先說一下這樣做帶來的好處

由上面j的變化可知，j的改變是每次移動兩步，所以，根據算法描述。所有和median相等的元素一定是最后才固定位置，又因為當j指向的值等于median時，是不與i和k指向的任何一個元素交換的。所以，每次移動兩步帶來的結果是這些median永遠不可能相鄰。換句話說就是永遠不會出現兩個median挨著的情況

---

對于j的移動算法，可以是

(1 + 2 * j) % (n | 1);

另j從0開始，那么j實際指向的位置由上面的式子確定，每次移動后j += 1

(n | 1)的目的是將n變為奇數，因為只有奇數才可以每次移動兩步時不重復，(1 + 2 * j)中加一的目的是讓j從奇數位置開始指

根據算法描述，i和k每次也應該是移動兩步，所以也可以利用上面的式子計算i和k實際指向的位置。

代碼如下

class Solution { public:void wiggleSort(vector<int>& nums) {int n = nums.size();/* 查找中位數 */auto middle = nums.begin() + n / 2;std::nth_element(nums.begin(), middle, nums.end());int median = *middle;/* lamda表達式，返回i, j, k實際指向的位置 */auto A = [n](int idx) { return (1 + 2 * idx) % (n | 1); };int i = 0, j = 0, k = n - 1;while(j <= k){/* 如果當前的元素大于median，就放在奇數位置上 *//* 這里的nums[A(i++)]的值也有可能是median，因為它在之前沒有被交換，而是在這里交換 *//* i和j起始位置相同，所以可以同時加一，而k不行 */if(nums[A(j)] > median)swap(nums[A(i++)], nums[A(j++)]);/* 如果當前的元素小于median，就放在偶數位置上 *//* j不能加一是因為nums[A(k--)]的大小不確定，而與nums[A(i++)]交換時可以確定，因為之前的值一定大于等于median */else if(nums[A(j)] < median)swap(nums[A(j)], nums[A(k--)]);/* 如果和median相等，就遍歷下一個 */else++j;}} };

總結

以上是生活随笔為你收集整理的每天一道LeetCode-----对序列进行排序，要求nums[0] nums[1] nums[2] nums[3] ....的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。