Wiggle Sort II

這題其實就操作上不難, 但當下我不覺得有一般人能馬上想到最佳解

我們慢慢來吧

先不要用follow up的最佳解先解釋

首先, 我們要找到中間的那個數(mid)

所以我們先做排序, 然後直接取正中央的那個數,

我們做一個長度一樣的陣列, 裡面擺滿這個mid

接著, 我們從第一個(這邊注意, 不是第零個)index開始放大的數字, 然後一一放下來,每次都跳一個放, 直到放到數字已經比mid小了

再來, 我們在開始倒數第二個(總數為偶數時), 開始放比較小的數字, 依序放到數字比mid大

總數為基數時, 就是倒數第一個

示意圖

2,4,5,5,6,13

M: 5

L [6, 13]

S[2, 4]

[5,13,4,6,2,5]
 M          
   L    L   
      S   S  
            M

倘若五有三個呢？

[2,4,5,5,5,6,13]
=>
[5,13,5,6,4,5,2]
 M
   L    L   
          S   S
      M     M

為什麼我們可以這樣放呢

因為 無論是前面, 還是後面, 兩個S中間幾乎都是夾M

兩個L中間也是夾M

若個數為偶數

最中間的部分會形成LSLS

倘若為基數 最中間的部分會形成 MLS

所以剛好所有情況都可以解決

class Solution {
public:
  void wiggleSort(vector<int> &nums) {
    if (nums.size() <= 1) {
      return;
    }
    sort(nums.begin(), nums.end());
    int len = nums.size();
int mid = nums[len / 2];
    vector<int> ans(len, mid);
    int j = 1;
    int high = (len % 2 == 1) ? len - 1 : len - 2;
    for (int i = len - 1; i >= 0, nums[i] > mid; i--, j += 2) {
      ans[j] = nums[i];
    }
    for (int i = 0; i < len, nums[i] < mid; i++, high -= 2) {
      ans[high] = nums[i];
    }
    nums = ans;
  }
};

接著是follow up , 首先我們要用到c++的這個function, nth_element

這個是做什麼用的呢?他會幫你在一個陣列裡, 找到第n大的element, 並且幫助定位, 所以你只需指到n index, 及會是第n大的值

但0至n -1, n + 1-final

都不需要排序過

只是這個函數第n個的位址是給pointer, 使用上要注意一下

另外就是一個我覺得一般人應該也想不到的index轉換function

在上面的case中, 我們可以知道

0 ~ n -1 : S
n:M
n + 1 ~ final : L
所以我們可以這樣放
0, 1, 2, 3, 4: 原本的順位
1, 3, 0, 2, 4: 之後的順位

這有個跟鬼一樣的轉換function

int index(int pos, int len) { return (1 + pos * 2) % (len | 1); };

這個我覺得還是沒辦法想到

最後 i 從零開始換

基本上我沒看過再給我重新來好幾次也不會想到, 想要直接做就被下來吧

class Solution {
  public:
    int index(int pos, int len) { return (1 + pos * 2) % (len | 1); };
    void wiggleSort(vector<int> &nums) {
        nth_element(nums.begin(), nums.begin() + nums.size() / 2, nums.end());
        int len = nums.size(), low = 0, high = len - 1, mid = nums[len / 2],
            i = 0;
while (i <= high) {
            if (nums[index(i, len)] > mid)
                swap(nums[index(i++, len)], nums[index(low++, len)]);
            else if (nums[index(i, len)] < mid)
                swap(nums[index(i, len)], nums[index(high--, len)]);
            else
                i++;
        }
    }
};