系列文章目錄

---

前言

本人最近再練習算法，所以會發布自己的解題思路，希望大家多指教

一、題目描述

一貧如洗的樵夫阿里巴巴在去砍柴的路上，無意中發現了強盜集團的藏寶地，藏寶地有編號從0-N的箱子，每個箱子上面貼有箱子中藏有金幣的數量。

從金幣數量中選出一個數字集合，并銷毀貼有這些數字的每個箱子，如果能銷毀一半及以上的箱子，則返回這個數字集合的最小大小。

二、輸出描述

一個數字字串，數字之間使用逗號分隔，例如: 6,6,6,6,3,3,3,1,1,5字串中數字的個數為偶數，并且

1 <= 字串中數字的個數 <= 100000

1 <= 每個數字 <= 100000

三、輸入描述

這個數字集合的最小大小，例如: 2

四、java代碼

	public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int[] array = Arrays.stream(scanner.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();Map<Integer, Integer> map = new HashMap<>();//存放每個數字，及對應出現的次數for (int i = 0; i < array.length; i++) {map.put(array[i], map.getOrDefault(array[i], 0) + 1);}//根據出現次數倒序排序map = map.entrySet().stream().sorted(Map.Entry.comparingByValue((o1, o2) -> o2 - o1)).collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue, (o1,o2)->o1, LinkedHashMap::new));//獲取箱子數量的一半int mul = array.length / 2;//初始化箱子數量和int sum = 0;//初始化數字最小數量int num = 0;for (Map.Entry<Integer, Integer> entry : map.entrySet()) {num++;sum += entry.getValue();//箱子數量超過一半，則直接輸出最小數字集合大小if (sum >= mul) {System.out.println(num);return;}}}

五、測試用例

輸入：
1,2,3,4,5,5,5,4,4,3
輸出：