4种解法确定数组大小减半

文章目录题目解法一顺序求解解法二字典排序解法三分类统计解法四空间换时

文章目录

• • 题目
  • 解法一顺序求解
  • 解法二字典排序
  • 解法三分类统计
  • 解法四空间换时间

---

题目

给你一个整数数组 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

---

解法一顺序求解

思路最简单朴素的解法首先进行元素统计然后根据统计的结果按最大到小进行计算不过当前解法C#会在数据大的情况下超时而Python和GO不会超时测试用例有6万多个元素源码及超时用例如下https://www.zhenxiangsimple.com/files/tech/testCase20200202.txt

统计元素个数

按个数进行最大值累计相当于冒泡排序

• 时间复杂度O(n²)
• 空间复杂度O(n)

public class Solution {public int MinSetSize(int[] arr) {Dictionary r new Dictionary();for(int i0;i

解法二字典排序

思路基于解法一先对结果进行排序然后使用排序后的结果进行统计按道理解法一更快但可能.NET3.5对Dictionary的排序优化使得效率比自己查询更高。

• 时间复杂度不算排序部分O(n)
• 空间复杂度O(n)

public class Solution {public int MinSetSize(int[] arr) {Dictionary r new Dictionary();for(int i0;i arr.Length){return ct;} }return 0;//仅为编译}}

---

解法三分类统计

思路基于分类统计的思想首先将元素进行统计使用数组下标表示数组中元素个数数组元素的值表示不同元素的个数最后通过统计该数组下标即可。如果该元素为0则表示不存在当前个数数组下标对应的个数的元素。

统计数组中重复元素的个数放入数组r

对数组中元素个数进行统计判断

如果已经超出半数则减去重复的个数比如r[2]3表示有两个相同元素的元素有3个比如1,1,2,2,3,3,…那么不需要3个元素全部累计只需要满足超出半数即可因此需要把多余的元素减去。

• 时间复杂度O(n)
• 空间复杂度O(n)

public class Solution {public int MinSetSize(int[] arr) {int [] r new int[arr.Length1];//存储元素个数r[0] arr.Length;Dictionary d new Dictionary();foreach(int item in arr){if(d.ContainsKey(item)){//已有元素时累计d[item];}else{//新元素增加d.Add(item,1);}r[d[item]];r[d[item]-1]--;}int c 0,t 0,idx 0;for(int iarr.Length;i>0;i--){//从最大值到最小值进行统计if(r[i]>0){c i*r[i];tr[i];idx i;}if(c*2 > arr.Length){//如果超出限制则减去重复的部分t - (c*2 - arr.Length)/(2*i);break;}}return t;}}

---

解法四空间换时间

思路基于解法三的思路做一个变化将值和索引做个交换即使用一个大的空间索引即为值本身数组元素的值为该值对应的个数。缺点就是如果本身的值很大就比较耗费资源可以先便利一边找到最大值也可以直接选择一个相对大的值本次选择后者一个相对大的值110000开始选择10万提示越界改为11万可以了。

统计值的个数

对统计数组进行排序

将排序结果从大到小进行求解

• 时间复杂度O(n)不算排序部分
• 空间复杂度O(1)虽然是1,但其实最大

public class Solution {public int MinSetSize(int[] arr) {int[] r new int[110000];foreach(int item in arr){//元素个数统计r[item];}Array.Sort(r);//排序int c 0,ct 0;for(int ir.Length-1;i>0;i--){//个数计数c r[i];ct ;if(c*2 > arr.Length){return ct;} }return 0;//仅为编译}}