LeetCode每日一题(324. Wiggle Sort II)

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.

Follow Up: Can you do it in O(n) time and/or in-place with O(1) extra space?

---

nums = [1, 5, 1, 1, 6, 4]

1. 排序:

   [1, 1, 1, 4, 5, 6]

2. 组出所有"小于"的 pair

   paris = [[1, 4], [1, 5], [1, 6]]

   1 < 4
   1 < 5
   1 < 6

3. 用 pairs 组出所有"大于"的 pair

   (1 < 4) > (1 < 5) > (1 < 6)
   之所以能这样进行排布， 是因为对于任意的 pair[i], pair[i][0]一定是<=任意一个 pair[j][1]的, 但是这里要考虑 pair[i][1] == pair[j][0]的情况, 例如: nums=[4, 5, 5, 6], pairs = [[4, 5], [5, 6]], 此时[4, 5][1] == [5, 6][0], 如果我们按正序排列这两个 pairs 的话， 那就会变成(4 < 5) > (5 < 6), 中间的>显然是不成立的， 但是因为 pair[i][0] <= pair[j][1], 所以我们只需要把[5, 6]放到[4, 5]之前就好了， 因为题目中说只要有一个成立的答案， 所以左右两边必定有一个是可以放置的

这个思路肯定不是最优的， 而且实现也做的不好， 题目进一步提出了 O(n)复杂度的解法， 有兴趣的可以尝试解一下

---

impl Solution {
    
    pub fn wiggle_sort(nums: &mut Vec<i32>) {
    
        nums.sort();
        let mut pairs = Vec::new();
        let first_half = nums[..nums.len() / 2 + nums.len() % 2].to_vec();
        let second_half = nums[nums.len() / 2 + nums.len() % 2..].to_vec();
        for i in 0..first_half.len().max(second_half.len()) {
    
            let mut p = vec![first_half[i]];
            if i < second_half.len() {
    
                p.push(second_half[i]);
            }
            pairs.push(p);
        }
        let mut ans = Vec::new();
        while !pairs.is_empty() {
    
            let mut p = pairs.remove(0);
            if let Some(last) = ans.pop() {
    
                if last == p[0] {
    
                    ans.push(last);
                    p.append(&mut ans);
                    ans = p;
                } else {
    
                    ans.push(last);
                    ans.append(&mut p);
                }
                continue;
            }
            ans.append(&mut p);
        }
        *nums = ans;
    }
}