Question

1338. 数组大小减半

English Version

题目描述

给你一个整数数组 arr。你可以从中选出一个整数集合，并删除这些整数在数组中的每次出现。

返回 至少 能删除数组中的一半整数的整数集合的最小大小。

 

示例 1：

输入：arr = [3,3,3,3,5,5,5,2,2,7]
输出：2
解释：选择 {3,7} 使得结果数组为 [5,5,5,2,2]、长度为 5（原数组长度的一半）。
大小为 2 的可行集合有 {3,5},{3,2},{5,2}。
选择 {2,7} 是不可行的，它的结果数组为 [3,3,3,3,5,5,5]，新数组长度大于原数组的二分之一。

示例 2：

输入：arr = [7,7,7,7,7,7]
输出：1
解释：我们只能选择集合 {7}，结果数组为空。

 

提示：

• 1 <= arr.length <= 105
• arr.length 为偶数
• 1 <= arr[i] <= 105

解法

方法一：计数 + 排序

我们可以用哈希表或数组 $cnt$ 统计数组 $arr$ 中每个数字出现的次数，然后将 $cnt$ 中的数字从大到小排序，从大到小遍历 $cnt$，每次遍历将当前数字 $x$ 加入答案，并将 $m$ 加上 $x$，如果 $m \geq \frac{n}{2}$，则返回答案。

时间复杂度 $O(n \times \log n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 $arr$ 的长度。

class Solution:
  def minSetSize(self, arr: List[int]) -> int:
    cnt = Counter(arr)
    ans = m = 0
    for _, v in cnt.most_common():
      m += v
      ans += 1
      if m * 2 >= len(arr):
        break
    return ans

class Solution {
  public int minSetSize(int[] arr) {
    int mx = 0;
    for (int x : arr) {
      mx = Math.max(mx, x);
    }
    int[] cnt = new int[mx + 1];
    for (int x : arr) {
      ++cnt[x];
    }
    Arrays.sort(cnt);
    int ans = 0;
    int m = 0;
    for (int i = mx;; --i) {
      if (cnt[i] > 0) {
        m += cnt[i];
        ++ans;
        if (m * 2 >= arr.length) {
          return ans;
        }
      }
    }
  }
}

class Solution {
public:
  int minSetSize(vector<int>& arr) {
    int mx = *max_element(arr.begin(), arr.end());
    int cnt[mx + 1];
    memset(cnt, 0, sizeof(cnt));
    for (int& x : arr) {
      ++cnt[x];
    }
    sort(cnt, cnt + mx + 1, greater<int>());
    int ans = 0;
    int m = 0;
    for (int& x : cnt) {
      if (x) {
        m += x;
        ++ans;
        if (m * 2 >= arr.size()) {
          break;
        }
      }
    }
    return ans;
  }
};

func minSetSize(arr []int) (ans int) {
  mx := slices.Max(arr)
  cnt := make([]int, mx+1)
  for _, x := range arr {
    cnt[x]++
  }
  sort.Ints(cnt)
  for i, m := mx, 0; ; i-- {
    if cnt[i] > 0 {
      m += cnt[i]
      ans++
      if m >= len(arr)/2 {
        return
      }
    }
  }
}

function minSetSize(arr: number[]): number {
  const counter = new Map<number, number>();
  for (const v of arr) {
    counter.set(v, (counter.get(v) ?? 0) + 1);
  }
  const t = Array.from(counter.values());
  t.sort((a, b) => b - a);
  let ans = 0;
  let n = 0;
  for (const cnt of t) {
    n += cnt;
    ++ans;
    if (n * 2 >= arr.length) {
      break;
    }
  }
  return ans;
}