LeetCode #1338 Reduce Array Size to The Half Solution & Explanation - Zyrastory

Content

Post Views: 7

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 res

Runtime : 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

Latest Post