LeetCode #1338 Reduce Array Size to The Half 將陣列的數量減至一半

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;
        
    }
}

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;
        
    }
}

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

/**
 * @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;;
};