Leetcode 2856. Minimum Array Length After Pair Removals

Example 1:

Input: nums = [1,3,4,9]
Output: 0
Explanation: Initially, nums = [1, 3, 4, 9].
In the first operation, we can choose index 0 and 1 because nums[0] < nums[1] <=> 1 < 3.
Remove indices 0 and 1, and nums becomes [4, 9].
For the next operation, we can choose index 0 and 1 because nums[0] < nums[1] <=> 4 < 9.
Remove indices 0 and 1, and nums becomes an empty array [].
Hence, the minimum length achievable is 0.
Example 2:

Input: nums = [2,3,6,9]
Output: 0
Explanation: Initially, nums = [2, 3, 6, 9].
In the first operation, we can choose index 0 and 2 because nums[0] < nums[2] <=> 2 < 6.
Remove indices 0 and 2, and nums becomes [3, 9].
For the next operation, we can choose index 0 and 1 because nums[0] < nums[1] <=> 3 < 9.
Remove indices 0 and 1, and nums becomes an empty array [].
Hence, the minimum length achievable is 0.
Example 3:

Input: nums = [1,1,2]
Output: 1
Explanation: Initially, nums = [1, 1, 2].
In an operation, we can choose index 0 and 2 because nums[0] < nums[2] <=> 1 < 2.
Remove indices 0 and 2, and nums becomes [1].
It is no longer possible to perform an operation on the array.
Hence, the minimum achievable length is 1.

Constraints:

1 <= nums.length <= 105
1 <= nums[i] <= 109
nums is sorted in non-decreasing order.

簡單來說 nums[i] < nums[j] 就可以消除 , 要找消到最後的 array 長度

解法 : 這種消除類的題目有一個技巧 , 重複的數字要最早消
就數學上先解釋:
1.如果重複出現最多的數沒有超過一半 , 那代表他自己可以被完全消除
e.g. [1,1,1,1,2,3,4,5,6] , 1出現4次 其他數字5次 , 那1絕對可以消除完畢 , 最後剩餘一個其他數字

2.如果重複出現最多的數有超過一半 , 那代表他可以把其他人完全消除
e.g. [1,1,1,1,1,3,4,5,6] , 1出現5次 其他數字4次 , 那其他數字絕對可以消除完畢 , 最後剩餘一個1

上述兩種情況化作公式
1.重複最多的數不超過一半 , 兩兩必能消除 , 最後只會剩下 0 or 1 , 所以剩下 n%2個;
2.重複最多的數超過一半 , 消完只剩自己 , 自己重複出現 maxi次 , 自己以外有 n-maxi個 , 所以會剩下 maxi - (n-maxi) = 2*maxi-n個

class Solution {
public:    
    int minLengthAfterRemovals(vector<int>& nums) {
        unordered_map<int, int> mp;
        int n= nums.size();
        for (int num : nums) {
            mp[num]++; //紀錄每個數字出現次數
        }
        
        int maxi =0;
        for (auto it:mp){
            maxi = max(maxi,it.second); //找出現最多次是幾次
        }

        if(maxi <= n/2){
            return n%2;
        }else{
            return 2*maxi - n;
        }
    }
};