Question

1481. Least Number of Unique Integers after K Removals

中文文档

Description

Given an array of integers arr and an integer k. Find the _least number of unique integers_ after removing exactly k elements.

 

Example 1:

Input: arr = [5,5,4], k = 1

Output: 1

Explanation: Remove the single 4, only 5 is left.

Example 2:

Input: arr = [4,3,1,1,3,3,2], k = 3

Output: 2

Explanation: Remove 4, 2 and either one of the two 1s or three 3s. 1 and 3 will be left.

 

Constraints:

• 1 <= arr.length <= 10^5
• 1 <= arr[i] <= 10^9
• 0 <= k <= arr.length

Solutions

Solution 1: Hash Table + Sorting

We use the hash table $cnt$ to count the number of times each integer in the array $arr$ appears, and then sort the values in $cnt$ in ascending order, and record them in the array $nums$.

Next, we traverse the array $nums$. For the current value that we traverse to $nums[i]$, we subtract $k$ by $nums[i]$. If $k \lt 0$, it means that we have removed $k$ elements, and the minimum number of different integers in the array is the length of $nums$ minus the index $i$ that we traverse to at the current time. Return directly.

If we traverse to the end, it means that we have removed all the elements, and the minimum number of different integers in the array is $0$.

The time complexity is $O(n \times \log n)$, and the space complexity is $O(n)$, where $n$ is the length of the array $arr$.

class Solution:
  def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
    cnt = Counter(arr)
    for i, v in enumerate(sorted(cnt.values())):
      k -= v
      if k < 0:
        return len(cnt) - i
    return 0

class Solution {
  public int findLeastNumOfUniqueInts(int[] arr, int k) {
    Map<Integer, Integer> cnt = new HashMap<>();
    for (int x : arr) {
      cnt.merge(x, 1, Integer::sum);
    }
    List<Integer> nums = new ArrayList<>(cnt.values());
    Collections.sort(nums);
    for (int i = 0, m = nums.size(); i < m; ++i) {
      k -= nums.get(i);
      if (k < 0) {
        return m - i;
      }
    }
    return 0;
  }
}

class Solution {
public:
  int findLeastNumOfUniqueInts(vector<int>& arr, int k) {
    unordered_map<int, int> cnt;
    for (int& x : arr) {
      ++cnt[x];
    }
    vector<int> nums;
    for (auto& [_, c] : cnt) {
      nums.push_back(c);
    }
    sort(nums.begin(), nums.end());
    for (int i = 0, m = nums.size(); i < m; ++i) {
      k -= nums[i];
      if (k < 0) {
        return m - i;
      }
    }
    return 0;
  }
};

func findLeastNumOfUniqueInts(arr []int, k int) int {
  cnt := map[int]int{}
  for _, x := range arr {
    cnt[x]++
  }
  nums := make([]int, 0, len(cnt))
  for _, v := range cnt {
    nums = append(nums, v)
  }
  sort.Ints(nums)
  for i, v := range nums {
    k -= v
    if k < 0 {
      return len(nums) - i
    }
  }
  return 0
}

function findLeastNumOfUniqueInts(arr: number[], k: number): number {
  const cnt: Map<number, number> = new Map();
  for (const x of arr) {
    cnt.set(x, (cnt.get(x) || 0) + 1);
  }
  const nums: number[] = [];
  for (const [_, v] of cnt) {
    nums.push(v);
  }
  nums.sort((a, b) => a - b);
  for (let i = 0; i < nums.length; ++i) {
    k -= nums[i];
    if (k < 0) {
      return nums.length - i;
    }
  }
  return 0;
}