专栏导读
本专栏收录于《华为OD机试（JAVA）真题（A卷+B卷）》。
刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。
一、题目描述
一贫如洗的樵夫阿里巴巴在去砍柴的路上，无意中发现了强盗集团的藏宝地，藏宝地有编号从0-N的箱子，每个箱子上面贴有箱子中藏有金币的数量。
从金币数量中选出一个数字集合，并销毁贴有这些数字的每个箱子，如果能销毁一半及以上的箱子，则返回这个数字集合的最小大小。
二、输入描述
一个数字字串，数字之间使用逗号分隔，例如: 6,6,6,6,3,3,3,1,1,5字串中数字的个数为偶数，并且
1 <= 字串中数字的个数 <= 100000
1 <= 每个数字 <= 100000
三、输出描述
这个数字集合的最小大小，例如: 2
四、解题思路
1、题目关键点：
从金币数量中选出一个数字集合，并销毁贴有这些数字的每个箱子，如果能销毁一半及以上的箱子，则返回这个数字集合的最小大小。
2、大白话的意思就是
一个包含若干个正整数的数组，从中取出某些数字，最少取几次可以使取出数字的个数大于等于原有数组的一半。
3、比如
数组[1,2,3,3,3]，第一次取出3，取了3个，大于等于原有数组的一半，搞定。
问题的关键是，要取出原有数组中个数最多的那个数字，和一半比较，再取第二多的，循环往复，次数绝对最少。
4、思路这不就来了
- 先找出数组中个数最多的数字，不，是按个数降序排序；
- 然后从降序数组中取数字，和原数组大小的一半（奇数的话向上取整）进行比较，大于等于即可；
- 输出一共取了几次。
五、Java算法源码
package com.guor.od;
import java.util.Scanner;
import java.util.*;
import java.util.HashMap;
public class OdTest {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 若干个带有数字的箱子
String[] arr = sc.nextLine().split(",");
/**
* 数组中每个数字的个数
* key：数字
* value：个数
*/
Map<String, Integer> map = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
String str = arr[i];
map.put(str, map.getOrDefault(str, 0) + 1);
}
// 按照数字的个数，降序排序
List<Map.Entry<String, Integer>> mapList = new ArrayList<>(map.entrySet());
mapList.sort((a, b) -> {
return b.getValue() - a.getValue();
});
// 取出数字的个数之和
int count = 0;
// 原数组长度的一半，奇数的话向上取整
int half = (int) Math.ceil((double) arr.length / 2);
// 取了几次
int step = 0;
for (int i = 0; i < mapList.size(); i++) {
// 某数字的个数
count += mapList.get(i).getValue();
step++;
// 取出的个数大于等于原数组的一半
if (count >= half) {
break;
}
}
// 输出一共取了几次
System.out.println(step);
}
}
六、效果展示
1、输入
1,2,3,4,5,5,5,4,4,3
2、输出
2
3、说明
- 一共10个数字，一半是5；
- 按个数降序排序3个4,3个5，2个3，1个2，1个1，[4,4,4,5,5,5,3,3,1,2]
- 先取出4，剩余[5,5,5,3,3,1,2]，取出3个4，小于一半5；
- 再取5，剩余[3,3,1,2]，取出3个5，上一次取3个4，共取出6个，大于等于一半5；
- 输出取出次数2；
🏆下一篇：华为OD机试真题 Java 实现【路灯照明问题】【2022Q4 100分】，感谢fly晨发现这个问题，并提供更优质的算法
🏆本文收录于，华为OD机试（JAVA）真题（A卷+B卷）
刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。