Leetcode刷题之路——1338.数组大小减半
本文最后更新于:2020年12月2日 凌晨
题目描述
给你一个整数数组 arr
。你可以从中选出一个整数集合,并删除这些整数在数组中的每次出现。
返回 至少 能删除数组中的一半整数的整数集合的最小大小。
示例 1:
输入:arr = [3,3,3,3,5,5,5,2,2,7]
输出:2
解释:选择 {3,7} 使得结果数组为 [5,5,5,2,2]、长度为 5(原数组长度的一半)。
大小为 2 的可行集合有 {3,5},{3,2},{5,2}。
选择 {2,7} 是不可行的,它的结果数组为 [3,3,3,3,5,5,5],新数组长度大于原数组的二分之一。
示例 2:
输入:arr = [7,7,7,7,7,7]
输出:1
解释:我们只能选择集合 {7},结果数组为空。
示例 3:
输入:arr = [1,9]
输出:1
示例 4:
输入:arr = [1000,1000,3,7]
输出:1
示例 5:
输入:arr = [1,2,3,4,5,6,7,8,9,10]
输出:5
提示:
-
1 <= arr.length <= 10^5
-
arr.length
为偶数 -
1 <= arr[i] <= 10^5
题目分析
个人初尝试
显然,这个题目涉及到了数据的存储,我需要知道每个数字存在多少个,才能去选择删减。删减的思路也挺直接的,从最大的删减起,当删去后的数组大小小于或等于原长度的一半,当作删减完成,返回删减的元素数值。
设及存储,显然用数组来存是不大理智的,因为我们需要同时储存数字和个数。直接定义数组只能把下标当作数字,那就给排序带来了相当大的麻烦,且空间上不方便开辟。那么自然的,想到用 map
来存储,用一对键值对来存储数字和个数。
排序方面自然是想要用 sort()
进行排序,而且降序排序就足够了。但是无法对 map
来进行降序排序,所以在 map
生成后,我们还需要把生成的 map
中的数据转存出来。因为数字数目的不确定,而且我们的输出值不需要知道要删去哪些数字。那么,我们就用一个 vector
保存 map
中个数的那一栏就好了,然后再排序,开始进行计算。
仔细想想,不需要进行 map
的排序(因为按照key值排序没有意义),那么使用 unordered_map
似乎是一个更有助于性能提升的选择。
具体代码实现如下
class Solution {
public:
int minSetSize(vector<int>& arr) {
int count = 0;
int cutsize = 0;
unordered_map<int,int>umap;
//循环构建map
for(int i = 0; i < arr.size(); ++i) {
umap[arr[i]]++;
}
vector<int>numlist;
//循环构建vector
for(int i = 0; i < umap.size(); ++i) {
numlist.push_back(umap[i]);
}
//对vector进行排序
sort(numlist.begin(), numlist.end(), greater<int>());
//循环开始计算
for(int i = 0; i < numlist.size(); ++i) {
if(cutsize * 2 >= arr.size()) {
return count;
}
cutsize += numlist[i];
count++;
}
}
};
第一次提交无法通过,提示我编译出错,没有 return
。。。。。。于是在最后一个 for
循环外面加了一个 return count;
运行通过,但是效率么。。。。。低的吓人。
调优
看了看官方给出的代码,思路和我是一样的,但是性能却提高特别多。代码如下
class Solution {
public:
int minSetSize(vector<int>& arr) {
unordered_map<int, int> freq;
for (int num: arr) {
++freq[num];
}
vector<int> occ;
for (auto& [k, v]: freq) {
occ.push_back(v);
}
sort(occ.begin(), occ.end(), greater<int>());
int cnt = 0, ans = 0;
for (int c: occ) {
cnt += c;
ans += 1;
if (cnt * 2 >= arr.size()) {
break;
}
}
return ans;
}
};
显然,肯定是 for
循环的用法带来的巨大提升。
经过测试,将原先的代码中更改为官方给出的样式,发现如下语句的更改性能提升巨大
for (auto& [k, v]: freq) {
occ.push_back(v);
}
式子中的 &
可以去掉,因为这表示可以取出的 [k, v]
进行修改,但实际上我们不需要修改。
经分析,使用 i
来循环,每次都蕴藏了一个查询的过程,自然会消耗不少的资源。而利用这样的基于范围的 for
,就不存在这样的问题。经测试,将循环量从 i
替换成 map
的迭代器,也是同样层次的性能提升。
一些细节的总结
- 关于
sort()
-
#include <algorithm>
- 前两个参数是范围,第三个参数是排序方法
- 排序方法可自定义,为
bool
的返回,两个输入 - 已定义好的排序方法(记得后面加括号)
-
equal_to<Type>
-
not_equal_to<Type>
-
greater<Type>
-
greater_equal<Type>
-
less<Type>
-
less_equal<Type>
-
-
- 基于范围的
for
以后可以多用用 - 注意
map
中的查询,要遍历还是得依靠迭代器 -
auto
是个好东西,活用
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!