leetcode-324 - Wiggle Sort II

動機

神奇的indexing

Problem

Given an integer array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]....

You may assume the input array always has a valid answer.

Example 1:

Input: nums = [1,5,1,1,6,4]Output: [1,6,1,5,1,4]Explanation: [1,4,1,5,1,6] is also accepted.

Example 2:

Input: nums = [1,3,2,2,3,1]Output: [2,3,1,3,1,2]

Constraints:

• 1 <= nums.length <= 5 * 104
• 0 <= nums[i] <= 5000
• It is guaranteed that there will be an answer for the given input nums.

Sol

每次遇到整數除法都很頭痛，如果沒有處理好就是錯

排序後折半，從最後去塞

這裡要讓小的部分多拿一點，看奇數長度的例子，就會發現小的一定在最後一個

class Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        tmp = [x for x in nums]
        tmp.sort()
        
        a = (len(nums)//2 if len(nums) % 2 == 0 else (len(nums)+1)//2)-1
        # a = ((len(nums)+1)//2)-1
        b = len(nums)-1
        for i in range(len(nums)):
            if i % 2 == 0:
                nums[i] = tmp[a]
                a -= 1
            else:
                nums[i] = tmp[b]
                b -= 1

Case study

第一個是用nth_element把array分成左右兩邊

第二個用A(i)把

• A的前半對應到nums上應該放大數字的部分
• A的後半對應到nums上應該放小數字的部分

Accessing A(0) actually accesses nums[1].
Accessing A(1) actually accesses nums[3].
Accessing A(2) actually accesses nums[5].
Accessing A(3) actually accesses nums[7].
Accessing A(4) actually accesses nums[9].
Accessing A(5) actually accesses nums[0].
Accessing A(6) actually accesses nums[2].
Accessing A(7) actually accesses nums[4].
Accessing A(8) actually accesses nums[6].
Accessing A(9) actually accesses nums[8].

從上面可以看出，在替A(i)切半時應該把前半的長度壓小一點，理由在Sol，所以這邊mid就是直接除2就好

void wiggleSort(vector<int>& nums) {
    int n = nums.size();
    
    // Find a median.
    auto midptr = nums.begin() + n / 2;
    nth_element(nums.begin(), midptr, nums.end());
    int mid = *midptr;
    
    // Index-rewiring.
    #define A(i) nums[(1+2*(i)) % (n|1)]

    // j :: iterate through A()
    int i = 0, j = 0, k = n - 1;
    while (j <= k) {
        if (A(j) > mid)
            swap(A(i++), A(j++)); // expand 大數字的範圍
        else if (A(j) < mid)
            swap(A(j), A(k--)); // expand 小數字的範圍
        else
            j++;
    }
}