LeetCode Problem
You are given an integer array arr. You can choose a set of integers and remove all the occurrences of these integers in the array.
Return the minimum size of the set so that at least half of the integers of the array are removed.
Solution
In this problem, my solution is to get the count of each integer first. Than let’s order by the count descending. After that, we can use a easy iteration to count the answer.
C# Solution
Solution1 – Dictionary + Linq (Sort by dict value)
public class Solution {
public int MinSetSize(int[] arr) {
//0. half number
int mid = arr.Length/2;
//1. init dict
Dictionary<int,int> dict = new Dictionary<int,int>();
foreach(var i in arr)
{
if (!dict.ContainsKey(i))
{
dict.Add(i, 1);
}
else
{
dict[i] = dict[i]+1;
}
}
//2. check > order by dict value(count)
var sortedDict = from entry in dict orderby entry.Value descending select entry.Value;
int res = 0;
foreach(var s in sortedDict)
{
if (s>mid)
{
return res == 0 ? 1 : res+1;
}
else if (s<mid)
{
mid -= s;
res +=1;
}
else //s == mid
{
return res+1;
}
}
return res;
}
}In this solution, we use Dictionary to store the count of each integer.
Runtime : 236ms、231ms、283ms
Java Solution
Solution1 – Map
class Solution {
public int minSetSize(int[] arr) {
//0. half number
int mid = arr.length/2;
//1. init map
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i : arr)
{
if (!map.containsKey(i))
{
map.put(i, 1);
}
else
{
map.replace(i, map.get(i)+1);
}
}
//2. check > order by map value(count)
Object[]vals = map.values().toArray();
Arrays.sort(vals, Collections.reverseOrder());
int res = 0;
for(var v : vals)
{
int s= (Integer)v;
if (s>mid)
{
return res == 0 ? 1 : res+1;
}
else if (s<mid)
{
mid -= s;
res +=1;
}
else //s == mid
{
return res+1;
}
}
return res;
}
}Runtime : 35ms、68ms、35ms
Python3 Solution
Solution1 – dictionary
class Solution:
def minSetSize(self, arr: List[int]) -> int:
mid = len(arr)/2
#init dictionary
d = {} #dict
for i in range(len(arr)):
if(arr[i] in d):
d[arr[i]] = d[arr[i]]+1
else:
d[arr[i]] = 1
#2. check > order by dict value(count)
d = dict(sorted(d.items(), key=lambda item: item[1], reverse=True))
res = 0
for s in d.values():
if (s>mid):
return 1 if res == 0 else res+1
elif (s<mid):
mid -= s
res +=1
else: #s == mid
return res+1
return resRuntime : 695ms、707ms、659ms
JavaScript Solution
Solution1 – dictionary
/**
* @param {number[]} arr
* @return {number}
*/
var minSetSize = function(arr) {
var mid = arr.length/2;
//1. init dict
var dict = { };
arr.forEach(function(item){
if(!(item in dict))
{
dict[item] = 1;
}
else
{
dict[item] = dict[item]+1;
}
});
//2.order by values
var k = Object.values(dict);
k.sort();
k = k.reverse();
//3.find result
var res = 0;
for (let i = 0; i < k.length; i++) {
const s = k[i];
if (s>mid)
{
return res == 0 ? 1 : res+1;
}
else if (s<mid)
{
mid -= s;
res +=1;
}
else //s == mid
{
return res+1;
}
}
return res;;
};Runtime : 140ms、191ms、160ms ≈ Faster than 70~90% ( maybe we can find a faster solution…)
Submission Detail
C#
Java
Python3
JavaScript
Conclusion
🧡If my solution helps, that is my honor!
🧡You can support me by clicking some ad, Thanks a lot
✅If you got any problem about the explanation or you need other programming language solution, please feel free to let me know (either leave a comment or contact me by Messenger is ok!)
"To be prepared is half the victory."
Miguel de Cervantes The problem link : Reduce Array Size to The Half – LeetCode
Reference
- c# – How do you sort a dictionary by value? – Stack Overflow
- python – How do I sort a dictionary by value? – Stack Overflow
Latest Post