华为OD机试 - 找磨损度最高和最低的硬盘 - 优先队列（Python/JS/C/C++ 2024 D卷 200分）

在这里插入图片描述

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

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新。

一、题目描述

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

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

二、输入描述

一组硬盘磨损度的数组。

说明:

(1) 数组endurances中无重复值

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

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

三、输出描述

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

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

四、测试用例

测试用例1：

1、输入

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

2、输出

5 8 9
0 6 7

测试用例2：

1、输入

9999 8888 7777 6666 5555 4444 3333

2、输出

0 1 2
4 5 6

3、说明

磨损度最高的三个值：9999（下标0）、8888（下标1）、7777（下标2）。
磨损度最低的三个值：5555（下标4）、4444（下标5）、3333（下标6）。

五、解题思路

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

六、Python算法源码

python">import heapqdef find_index(endurances, value):"""找到指定磨损度在数组中的下标"""for i, v in enumerate(endurances):if v == value:return ireturn -1def get_top_and_bottom_indexes(endurances):"""同时获取磨损度最高和最低的三个盘下标"""# 最小堆用于最高三个min_heap = []# 最大堆用于最低三个，Python中使用负数来模拟最大堆max_heap = []for value in endurances:# 维护最高三个heapq.heappush(min_heap, value)if len(min_heap) > 3:heapq.heappop(min_heap)  # 移除最小的，保留最大的三个# 维护最低三个heapq.heappush(max_heap, -value)if len(max_heap) > 3:heapq.heappop(max_heap)  # 移除最大的，保留最小的三个# 收集最高三个top3 = []while min_heap:top3.append(heapq.heappop(min_heap))top3.reverse()  # 降序# 收集最低三个bottom3 = []while max_heap:bottom3.append(-heapq.heappop(max_heap))bottom3.reverse()  # 升序# 获取对应的下标result = []for val in top3:result.append(find_index(endurances, val))for val in bottom3:result.append(find_index(endurances, val))# 对最高三个下标排序top_indexes = sorted(result[:3])# 对最低三个下标排序bottom_indexes = sorted(result[3:6])return top_indexes, bottom_indexesdef main():# 读取输入endurances = list(map(int, input().split()))top_indexes, bottom_indexes = get_top_and_bottom_indexes(endurances)# 输出结果print(' '.join(map(str, top_indexes)))print(' '.join(map(str, bottom_indexes)))if __name__ == "__main__":main()

七、JavaScript算法源码

javascript">function findIndex(endurances, value) {/*** 找到指定磨损度在数组中的下标*/for(let i=0;i<endurances.length;i++) {if(endurances[i] === value) {return i;}}return -1;
}function getTopAndBottomIndexes(endurances) {/*** 同时获取磨损度最高和最低的三个盘下标*/// 最小堆用于最高三个let minHeap = [];// 最大堆用于最低三个let maxHeap = [];for(let value of endurances) {// 维护最高三个minHeap.push(value);minHeap.sort((a,b) => a - b); // 升序if(minHeap.length >3) {minHeap.shift(); // 移除最小的}// 维护最低三个maxHeap.push(value);maxHeap.sort((a,b) => b - a); // 降序if(maxHeap.length >3) {maxHeap.shift(); // 移除最大的}}// 收集最高三个let top3 = minHeap.reverse(); // 降序// 收集最低三个let bottom3 = maxHeap.reverse(); // 升序// 获取对应的下标let result = [];for(let val of top3) {result.push(findIndex(endurances, val));}for(let val of bottom3) {result.push(findIndex(endurances, val));}// 对最高三个下标排序let top_indexes = result.slice(0,3).sort((a,b) => a - b);// 对最低三个下标排序let bottom_indexes = result.slice(3,6).sort((a,b) => a - b);return [top_indexes, bottom_indexes];
}// 主函数
function main() {const fs = require('fs');const input = fs.readFileSync('/dev/stdin', 'utf8').trim();const endurances = input.split(' ').map(Number);const [top_indexes, bottom_indexes] = getTopAndBottomIndexes(endurances);console.log(top_indexes.join(' '));console.log(bottom_indexes.join(' '));
}main();

八、C算法源码

#include <stdio.h>
#include <stdlib.h>// 函数用于比较两个整数，用于qsort
int compare(const void* a, const void* b) {return (*(int*)a - *(int*)b);
}// 找到指定磨损度在数组中的下标
int findIndex(int endurances[], int length, int value) {for(int i=0;i<length;i++) {if(endurances[i] == value) {return i;}}return -1;
}int main(){int endurances[200];int n=0;// 读取输入while(scanf("%d", &endurances[n]) != EOF){n++;}// 复制数组用于排序int sorted_asc[200];int sorted_desc[200];for(int i=0;i<n;i++) {sorted_asc[i] = endurances[i];sorted_desc[i] = endurances[i];}// 升序排序qsort(sorted_asc, n, sizeof(int), compare);// 降序排序// 自定义比较函数int compare_desc(const void* a, const void* b){return (*(int*)b - *(int*)a);}qsort(sorted_desc, n, sizeof(int), compare_desc);// 获取最高三个int top3[3];for(int i=0;i<3;i++) {top3[i] = sorted_desc[i];}// 获取最低三个int bottom3[3];for(int i=0;i<3;i++) {bottom3[i] = sorted_asc[i];}// 获取对应的下标int top_indexes[3];int bottom_indexes[3];for(int i=0;i<3;i++) {top_indexes[i] = findIndex(endurances, n, top3[i]);}for(int i=0;i<3;i++) {bottom_indexes[i] = findIndex(endurances, n, bottom3[i]);}// 对下标排序// 简单冒泡排序for(int i=0;i<2;i++) {for(int j=0;j<2-i;j++) {if(top_indexes[j] > top_indexes[j+1]){int temp = top_indexes[j];top_indexes[j] = top_indexes[j+1];top_indexes[j+1] = temp;}if(bottom_indexes[j] > bottom_indexes[j+1]){int temp = bottom_indexes[j];bottom_indexes[j] = bottom_indexes[j+1];bottom_indexes[j+1] = temp;}}}// 输出结果for(int i=0;i<3;i++) {printf("%d", top_indexes[i]);if(i !=2) printf(" ");}printf("\n");for(int i=0;i<3;i++) {printf("%d", bottom_indexes[i]);if(i !=2) printf(" ");}return 0;
}

九、C++算法源码

#include <bits/stdc++.h>
using namespace std;// 找到指定磨损度在数组中的下标
int findIndex(int endurances[], int length, int value){for(int i=0;i<length;i++){if(endurances[i] == value){return i;}}return -1;
}int main(){vector<int> endurances;int num;// 读取输入while(cin >> num){endurances.push_back(num);}int n = endurances.size();// 复制数组用于排序vector<int> sorted_asc = endurances;vector<int> sorted_desc = endurances;// 升序排序sort(sorted_asc.begin(), sorted_asc.end());// 降序排序sort(sorted_desc.begin(), sorted_desc.end(), greater<int>());// 获取最高三个vector<int> top3(sorted_desc.begin(), sorted_desc.begin()+3);// 获取最低三个vector<int> bottom3(sorted_asc.begin(), sorted_asc.begin()+3);// 获取对应的下标vector<int> top_indexes, bottom_indexes;for(auto val: top3){top_indexes.push_back(findIndex(&endurances[0], n, val));}for(auto val: bottom3){bottom_indexes.push_back(findIndex(&endurances[0], n, val));}// 对下标排序sort(top_indexes.begin(), top_indexes.end());sort(bottom_indexes.begin(), bottom_indexes.end());// 输出结果for(int i=0;i<top_indexes.size();i++){cout << top_indexes[i];if(i != top_indexes.size()-1) cout << " ";}cout << "\n";for(int i=0;i<bottom_indexes.size();i++){cout << bottom_indexes[i];if(i != bottom_indexes.size()-1) cout << " ";}return 0;
}

🏆下一篇：华为OD机试真题 - 简易内存池（Python/JS/C/C++ 2024 E卷 200分）

🏆本文收录于，华为OD机试真题（Python/JS/C/C++）

在这里插入图片描述