Keshawn_lu's Blog

Leetcode 5437. 不同整数的最少数目

字数统计: 529阅读时长: 2 min
2020/06/14 Share

题目简介:

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

示例 1:

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

示例 2:

1
2
3
输入: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

思路:

一开始的思路是先用哈希表存储每个数字出现的次数,然后去循环哈希表依次找到出现次数最少的值去删除。很遗憾这样做就超时了…

然后反向思路,去依次找出现次数最多的数字,直至sum >= arr.size() - k,很遗憾,因为还是要循环哈希表,和上述思路一样,还是超时了…

然后想到用vector<pair<int, int>>去存储哈希表中的键值对,然后自定义排序方法,使键值对以value的升序排序(从小到大),再去依次删除出现次数最少的数字,这样子终于过了…果然用vector排序还是比较好操作的。

tips:

  • 注意自定义排序方法的实现
  • 注意make_pair()函数的使用

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
bool cmp(const pair<int, int>& x, const pair<int, int>& y){

return x.second < y.second;
}

class Solution {
public:
int findLeastNumOfUniqueInts(vector<int>& arr, int k) {

unordered_map<int, int> map;

for(int i = 0; i < arr.size(); i++){

map[arr[i]]++;
}

vector<pair<int, int>> temp;

for (auto it = map.begin(); it != map.end(); it++) {

temp.push_back(make_pair(it->first, it->second));
}

sort(temp.begin(), temp.end(), cmp);

int sum = 0;
int count = 0;
for(int i = 0; i < temp.size(); i++){

sum += temp[i].second;
if(sum < k){

count++;
}

else if(sum == k){

count++;
break;
}
else{

break;
}
}

return temp.size() - count;

}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: