README.md

1481. 不同整数的最少数目

English Version

题目描述

给你一个整数数组 arr 和一个整数 k 。现需要从数组中恰好移除 k 个元素，请找出移除后数组中不同整数的最少数目。

 

示例 1：

输入：arr = [5,5,4], k = 1
输出：1
解释：移除 1 个 4 ，数组中只剩下 5 一种整数。

示例 2：

输入：arr = [4,3,1,1,3,3,2], k = 3
输出：2
解释：先移除 4、2 ，然后再移除两个 1 中的任意 1 个或者三个 3 中的任意 1 个，最后剩下 1 和 3 两种整数。

 

提示：

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

解法

Python3

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        counter = Counter(arr)
        t = sorted(counter.items(), key=lambda x: x[1])
        for v, cnt in t:
            if k >= cnt:
                k -= cnt
                counter.pop(v)
            else:
                break
        return len(counter)

Java

class Solution {
    public int findLeastNumOfUniqueInts(int[] arr, int k) {
        Map<Integer, Integer> counter = new HashMap<>();
        for (int v : arr) {
            counter.put(v, counter.getOrDefault(v, 0) + 1);
        }
        List<Map.Entry<Integer, Integer>> t = new ArrayList<>(counter.entrySet());
        Collections.sort(t, Comparator.comparingInt(Map.Entry::getValue));
        for (Map.Entry<Integer, Integer> e : t) {
            int v = e.getKey();
            int cnt = e.getValue();
            if (k >= cnt) {
                k -= cnt;
                counter.remove(v);
            } else {
                break;
            }
        }
        return counter.size();
    }
}

C++

class Solution {
public:
    int findLeastNumOfUniqueInts(vector<int>& arr, int k) {
        unordered_map<int, int> counter;
        for (int v : arr) ++counter[v];
        vector<pair<int, int>> t(counter.begin(), counter.end());
        sort(t.begin(), t.end(), [](const auto& a, const auto& b) { return a.second < b.second; });
        for (auto [v, cnt] : t) {
            if (k >= cnt) {
                k -= cnt;
                counter.erase(v);
            } else
                break;
        }
        return counter.size();
    }
};

Go

func findLeastNumOfUniqueInts(arr []int, k int) int {
	counter := make(map[int]int)
	for _, v := range arr {
		counter[v]++
	}
	var t [][]int
	for v, cnt := range counter {
		t = append(t, []int{v, cnt})
	}
	sort.Slice(t, func(i, j int) bool {
		return t[i][1] < t[j][1]
	})
	for _, e := range t {
		v, cnt := e[0], e[1]
		if k >= cnt {
			k -= cnt
			delete(counter, v)
		} else {
			break
		}
	}
	return len(counter)
}

...