Question

1338. Reduce Array Size to The Half

中文文档

Description

You are given an integer array arr. You can choose a set of integers and remove all the occurrences of these integers in the array.

Return _the minimum size of the set so that at least half of the integers of the array are removed_.

 

Example 1:

Input: arr = [3,3,3,3,5,5,5,2,2,7]
Output: 2
Explanation: Choosing {3,7} will make the new array [5,5,5,2,2] which has size 5 (i.e equal to half of the size of the old array).
Possible sets of size 2 are {3,5},{3,2},{5,2}.
Choosing set {2,7} is not possible as it will make the new array [3,3,3,3,5,5,5] which has a size greater than half of the size of the old array.

Example 2:

Input: arr = [7,7,7,7,7,7]
Output: 1
Explanation: The only possible set you can choose is {7}. This will make the new array empty.

 

Constraints:

• 2 <= arr.length <= 105
• arr.length is even.
• 1 <= arr[i] <= 105

Solutions

Solution 1

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;
}