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