Leetcode 2856. Minimum Array Length After Pair Removals

[Woodyiiiiiii]

Leetcode 2856. Minimum Array Length After Pair Removals

2576. Find the Maximum Number of Marked Indices

类似题目：
2576. Find the Maximum Number of Marked Indices

参考资料：
O(log n) 贪心+二分查找（Python/Java/C++/Go/JS）
一题四解 | 二分答案 + 双指针 + 找众数 + O(lgn)（Kotlin）

这道题我在竞赛中没做出来，还是缺少了一些灵性。我一开始的想法是对于某个元素，查找他大于它的最近的元素，然后抵消，但显然是错的；接着我又去查询大于它的最远的元素，也不行。显然，没有利用到贪心的思想。

贪心/脑筋急转弯

思路：算出众数，如果众数的出现频率大于数组长度的一半，那么除它之外的元素可以跟他抵消；否则，可以两两匹配，看数组长度是否是偶数，是的话能全部抵消，否则剩下1个。

class Solution {
    public int minLengthAfterRemovals(List<Integer> nums) {
        int n = nums.size();
      Map<Integer, Integer> cntMap = new HashMap<>();
      for (int num : nums) {
          cntMap.put(num, cntMap.getOrDefault(num, 0) + 1);
      }
      int maxOccur = 0;
      for (int key : cntMap.keySet()) {
          int val = cntMap.getOrDefault(key, 0);
          maxOccur = Math.max(maxOccur, val);
      }
      if (maxOccur > n / 2) {
        return 2 * maxOccur - n;
      } else {
        return n % 2 == 0 ? 0 : 1;
      }
    }
}

时间复杂度O(n)，空间复杂度O(n)。

二分

思路：根据匹配对数进行二分查询，每次对数组前m个数和后m个数进行匹配，放缩m。

class Solution {
    public int minLengthAfterRemovals(List<Integer> nums) {
        int n = nums.size();
        int l = 0, r = n / 2 + 1;
        while (l < r) {
            int m = (l + r) >> 1;
            if (ok(nums, m, n)) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        return n - 2 * (l - 1);
    }

    private boolean ok(final List<Integer> nums, int m, int n) {
        for (int i = 0, j = n - m; i < m && j < n; i++, j++) {
            if (nums.get(j) <= nums.get(i)) {
                return false;
            }
        }
        return true;
    }
}

时间复杂度O(nlgn)，空间复杂度O(1)。