华为OD机试 - 找磨损度最高和最低的硬盘 - 优先队列（Java 2024 C卷 100分）

在这里插入图片描述

华为OD机试 2024C卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（A卷+B卷+C卷）》。

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

存储阵列上使用的一批固态硬盘，根据硬盘磨损值给定一个数组endurances,数组中每个元素表示单块硬盘的磨损度(0到10000之间)。

磨损度越大，表示此盘需要更换的概率越高。需要找出磨损度最高三块盘下标和磨损度最低的三块盘下标。

二、输入描述

一组硬盘磨损度的数组。

说明:

(1) 数组endurances中无重复值

(2) 数组的长度范围:[6,200]

(3) 数组的下标从0开始。

三、输出描述

第一行:磨损度最高三块盘下标，按下标升序展示

第二行:磨损度最低的三块盘下标，按下标升序展示

1、输入

1 50 40 68 72 86 35 14 87 99 63 75

2、输出

5 8 9
0 6 7

四、解题思路

创建一个大小为 3 的最小堆（min heap）和一个大小为 3 的最大堆（max heap），用于存储磨损度最高的三块盘和最低的三块盘。
遍历硬盘磨损度的数组，将每个磨损度元素添加到堆中。
如果堆的大小超过 3，则将堆顶元素弹出，保持堆的大小为 3。
最后，将堆中的元素按顺序弹出，得到磨损度最高三块盘和最低三块盘的下标。
输出结果。

五、Java算法源码

java">public class OdTest01 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int[] endurances = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();int[] maxIndexes = getMaxIndexes(endurances);int[] minIndexes = getMinIndexes(endurances);// 输出结果System.out.println(Arrays.toString(minIndexes));System.out.println(Arrays.toString(maxIndexes));}// 获取磨损度最高三块盘下标public static int[] getMaxIndexes(int[] endurances) {// 创建一个最大堆PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());// 遍历磨损度数组，将每个元素添加到最大堆中for (int i = 0; i < endurances.length; i++) {maxHeap.offer(endurances[i]);// 如果堆的大小超过 3，则弹出堆顶元素if (maxHeap.size() > 3) {maxHeap.poll();}}// 将堆中的元素按顺序弹出，得到磨损度最高三块盘的下标int[] indexes = new int[3];for (int i = 0; i < 3; i++) {indexes[i] = findIndex(endurances, maxHeap.poll());}// 按下标升序排序Arrays.sort(indexes);return indexes;}// 获取磨损度最低三块盘下标public static int[] getMinIndexes(int[] endurances) {// 创建一个最小堆PriorityQueue<Integer> minHeap = new PriorityQueue<>();// 遍历磨损度数组，将每个元素添加到最小堆中for (int i = 0; i < endurances.length; i++) {minHeap.offer(endurances[i]);// 如果堆的大小超过 3，则弹出堆顶元素if (minHeap.size() > 3) {minHeap.poll();}}// 将堆中的元素按顺序弹出，得到磨损度最低三块盘的下标int[] indexes = new int[3];for (int i = 0; i < 3; i++) {indexes[i] = findIndex(endurances, minHeap.poll());}// 按下标升序排序Arrays.sort(indexes);return indexes;}// 找到指定磨损度在数组中的下标public static int findIndex(int[] endurances, int value) {for (int i = 0; i < endurances.length; i++) {if (endurances[i] == value) {return i;}}return -1;}
}