leetcode 1338. Reduce Array Size to The Half | 1338. 数组大小减半（Java）

淩亂°似流年 2022-10-13 12:57 6阅读 0赞

## 题目 ##

[https://leetcode.com/problems/reduce-array-size-to-the-half/][https_leetcode.com_problems_reduce-array-size-to-the-half]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

先统计每个数字出现次数，然后给出现次数排序。出现次数多者，先被选中。

比较简单，官方题解也是 O(nlogn) 的时间复杂度。不知道为啥是个 medium 题。

class Solution { 
        public int minSetSize(int[] arr) { 
            Map<Integer, Integer> map = new HashMap<>();
            for (Integer n : arr) { 
                if (map.containsKey(n)) map.put(n, map.get(n) + 1);
                else map.put(n, 1);
            }
    
            int[] count = new int[map.size()];
            int i = 0;
            for (Integer c : map.values())
                count[i++] = c;
            Arrays.sort(count);
    
            int sum = 0;
            i = count.length;
            while (sum < arr.length / 2) { 
                sum += count[--i];
            }
            return count.length - i;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

[https_leetcode.com_problems_reduce-array-size-to-the-half]: https://leetcode.com/problems/reduce-array-size-to-the-half/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20221005/4fda4d3f3e7c4fb8930e560d066363a8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20221005/1dd25a31613d47b2b4960ee8408cc4f5.png