class Solution {
public:
int findLeastNumOfUniqueInts(vector<int>& arr, int k) {
}
};
1481. 不同整数的最少数目
给你一个整数数组 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^51 <= arr[i] <= 10^90 <= k <= arr.length原站题解
golang 解法, 执行用时: 108 ms, 内存消耗: 15.1 MB, 提交时间: 2023-05-30 10:06:05
func findLeastNumOfUniqueInts(arr []int, k int) int {
cntMap := make(map[int]int)
for i := 0; i < len(arr); i++ {
cntMap[arr[i]]++
}
h := pairHeap{}
for n, c := range cntMap {
heap.Push(&h, pair{n, c})
}
for len(h) > 0 && h[0].cnt <= k {
top := heap.Pop(&h).(pair)
k -= top.cnt
}
return len(h)
}
type pair struct {
num int
cnt int
}
type pairHeap []pair
func (h pairHeap) Len() int { return len(h) }
func (h pairHeap) Less(i, j int) bool { return h[i].cnt < h[j].cnt }
func (h pairHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *pairHeap) Push(x interface{}) { *h = append(*h, x.(pair)) }
func (h *pairHeap) Pop() interface{} {
res := (*h)[len(*h)-1]
*h = (*h)[:len(*h)-1]
return res
}
golang 解法, 执行用时: 112 ms, 内存消耗: 13 MB, 提交时间: 2023-05-30 10:05:33
func findLeastNumOfUniqueInts(arr []int, k int) int {
m := map[int]int{}
target := []int{}
for _, num := range arr{
m[num]++
}
for k, _ := range m{
target = append(target, k)
}
sort.Slice(target, func(i, j int) bool{
return m[target[i]] < m[target[j]]
})
res := 0
for _, num := range target{
k -= m[num]
if k < 0{
res = len(m)
break
}
delete(m, num)
}
return res
}
golang 解法, 执行用时: 104 ms, 内存消耗: 13.2 MB, 提交时间: 2023-05-30 10:05:16
func findLeastNumOfUniqueInts(arr []int, k int) int {
// Map用来统计数字出现的频率
// Arr为数字出现频率数组
arrMap, arrNum := make(map[int]int), make([]int, 0)
for i := 0; i < len(arr); i ++ {
arrMap[arr[i]] ++
}
for _, num := range arrMap {
arrNum = append(arrNum, num)
}
// 排序
sort.Ints(arrNum)
cnt := 0
for i, v := range arrNum{
if k > v { // 若当前k大于该频率,则直接减
k -= v
} else if k == v { // 若等于,则最少数目为接下来数组的长度
cnt = len(arrNum) - i - 1
break
} else { // 若小于,则最少数目为当前数之后数组的长度
cnt = len(arrNum) - i
break
}
}
return cnt
}
javascript 解法, 执行用时: 84 ms, 内存消耗: 61.2 MB, 提交时间: 2023-05-30 10:04:32
/**
* @param {number[]} arr
* @param {number} k
* @return {number}
*/
var findLeastNumOfUniqueInts = function(arr, k) {
const map=new Map()
for(const n of arr){
map.set(n, map.has(n)? map.get(n)+1 : 1);
}
let count = map.size;
a: for (let j=1;j<=k;j++){
for (const n of map.values()) {
if (k <= 0) break a;
if (n === j) {
k-=n
if (k>=0) count-=1
}
}
}
return count;
};
java 解法, 执行用时: 48 ms, 内存消耗: 54.8 MB, 提交时间: 2023-05-30 10:04:13
class Solution {
public int findLeastNumOfUniqueInts(int[] arr, int k) {
Map<Integer, Integer> cntMap = new HashMap<>();
for(int num:arr) {
cntMap.put(num, cntMap.getOrDefault(num, 0)+1);
}
// 做一个排序操作
int ans = cntMap.size();
List<int[]> list = new ArrayList<>();
for(var entry:cntMap.entrySet()) {
list.add(new int[]{entry.getKey(), entry.getValue()});
}
list.sort(Comparator.comparingInt(a->a[1]));
for(int i = 0;i<list.size();i++) {
if(list.get(i)[1]>k) return ans;
ans--;
k-=list.get(i)[1];
}
return ans;
}
}
javascript 解法, 执行用时: 92 ms, 内存消耗: 64.6 MB, 提交时间: 2023-05-30 10:03:54
/**
* @param {number[]} arr
* @param {number} k
* @return {number}
*/
var findLeastNumOfUniqueInts = function(arr, k) {
const map = new Map()
for (let num of arr) {
map.set(num, (map.get(num) || 0) + 1)
}
const depth = []
for (let [_, val] of map) {
depth[val] = (depth[val] || 0) + 1
}
let res = _.sum(depth)
for (let i = 1; i < depth.length; i++) {
const diff = depth[i]
if (!diff) continue
if (k >= i * diff) {
res -= diff
k -= i * diff
} else if (k >= i) {
const index = (k / i) >> 0
res -= index
break
} else {
break
}
}
return res
};
java 解法, 执行用时: 45 ms, 内存消耗: 54.9 MB, 提交时间: 2023-05-30 10:03:29
class Solution {
public int findLeastNumOfUniqueInts(int[] arr, int k) {
Map<Integer, Integer> group = new HashMap<Integer, Integer>();
for (int num : arr) {
int count = group.getOrDefault(num, 0) + 1;
group.put(num, count);
}
List<int[]> freq = new ArrayList<int[]>();
for (Map.Entry<Integer, Integer> entry : group.entrySet()) {
int[] keyValue = {entry.getKey(), entry.getValue()};
freq.add(keyValue);
}
Collections.sort(freq, new Comparator<int[]>() {
public int compare(int[] keyValue1, int[] keyValue2) {
return keyValue1[1] - keyValue2[1];
}
});
int ans = freq.size();
for (int i = 0; i < freq.size(); i++) {
int occ = freq.get(i)[1];
if (k >= occ) {
--ans;
k -= occ;
} else {
break;
}
}
return ans;
}
}
python3 解法, 执行用时: 404 ms, 内存消耗: 36 MB, 提交时间: 2023-05-30 10:03:11
# 贪心，尽量先移除单个的，再双的
class Solution:
def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
group = collections.Counter(arr)
freq = group.most_common()[::-1]
ans = len(freq)
for _, occ in freq:
if k >= occ:
ans -= 1
k -= occ
else:
break
return ans