pythonjavacjsc_0">【华为OD-E卷-通信误码 100分(python、java、c++、js、c)】
题目
信号传播过程中会出现一些误码,不同的数字表示不同的误码ID,取值范围为1 ~ 65535,
用一个数组记录误码出现的情况,每个误码出现的次数代表误码频度,请找出记录中包含频度最高误码的最小子数组长度。
输入描述
- 误码总数目:取值范围为0~255,取值为 0 表示没有误码的情况。
误码出现频率数组:误码ID范围为1 ~ 65535,数组长度为1 ~ 1000
输出描述
- 包含频率最高的误码最小子数组长度
用例
用例一:
输入:
5
1 2 2 4 1
输出:
2
用例二:
输入:
7
1 2 2 4 2 1 1
输出:
4
python_51">python解法
- 解题思路:
- 目标: 找到数组中出现频率最高的元素,并返回包含该元素的最短子数组的长度。
解题步骤:
记录频率:用一个哈希表 freq_map 记录每个元素的出现次数。
记录首次出现位置:用一个哈希表 first_pos 记录每个元素第一次出现的索引。
更新最长频率和最短长度:
如果当前元素的频率超过已知的最大频率,则更新最大频率 max_freq 和对应的最短子数组长度 min_len。
如果频率相等,则比较当前子数组长度和已有的最短子数组长度,取较小值。
返回结果: 返回包含频率最高的元素的最短子数组的长度。
python">def find_min_length(arr):# 哈希表:记录每个元素的出现频率freq_map = {}# 哈希表:记录每个元素首次出现的位置first_pos = {}# 记录出现的最大频率max_freq = 0# 记录包含出现频率最高元素的最短子数组长度min_len = float('inf')# 遍历数组for i, num in enumerate(arr):# 更新频率freq_map[num] = freq_map.get(num, 0) + 1# 记录元素首次出现的位置if num not in first_pos:first_pos[num] = i# 获取当前元素的频率freq = freq_map[num]# 如果当前频率超过已知最大频率if freq > max_freq:max_freq = freqmin_len = i - first_pos[num] + 1 # 更新最短子数组长度# 如果频率相等,比较并更新最短子数组长度elif freq == max_freq:min_len = min(min_len, i - first_pos[num] + 1)# 返回最短子数组长度return min_lenif __name__ == "__main__":# 输入数组长度n = int(input())# 输入数组元素arr = list(map(int, input().split()))# 输出包含频率最高元素的最短子数组长度print(find_min_length(arr))
java_113">java解法
- 解题思路
- 目标: 找到数组中出现频率最高的元素,并返回包含该元素的最短子数组的长度。
解题步骤:
记录频率:使用 freqMap 记录每个元素的出现次数。
记录首次出现位置:使用 firstPos 记录每个元素第一次出现的索引。
更新最长频率和最短长度:
如果当前元素的频率超过已知的最大频率,则更新 maxFreq 和对应的最短子数组长度 minLen。
如果频率相等,则比较当前子数组长度和已有的最短子数组长度,取较小值。
最终结果: 返回包含频率最高的元素的最短子数组的长度。
java">import java.util.HashMap;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);// 读取数组长度int n = sc.nextInt();int[] arr = new int[n];// 读取数组元素for (int i = 0; i < n; i++) {arr[i] = sc.nextInt();}// 输出包含频率最高元素的最短子数组长度System.out.println(findMinLength(arr));}// 方法:找到包含频率最高元素的最短子数组长度public static int findMinLength(int[] arr) {// 哈希表:记录每个元素的出现频率HashMap<Integer, Integer> freqMap = new HashMap<>();// 哈希表:记录每个元素首次出现的位置HashMap<Integer, Integer> firstPos = new HashMap<>();// 记录出现的最大频率int maxFreq = 0;// 记录包含出现频率最高元素的最短子数组长度int minLen = Integer.MAX_VALUE;// 遍历数组for (int i = 0; i < arr.length; i++) {int num = arr[i];// 更新当前元素的出现频率freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);// 记录当前元素首次出现的位置if (!firstPos.containsKey(num)) {firstPos.put(num, i);}// 获取当前元素的出现频率int freq = freqMap.get(num);// 如果当前频率超过最大频率if (freq > maxFreq) {maxFreq = freq; // 更新最大频率minLen = i - firstPos.get(num) + 1; // 更新最短子数组长度}// 如果频率相等,比较并更新最短子数组长度else if (freq == maxFreq) {minLen = Math.min(minLen, i - firstPos.get(num) + 1);}}// 返回最短子数组长度return minLen;}
}
C++解法
- 解题思路
更新中
C解法
-
解题思路
-
目标: 找出数组中出现频率最高的错误类型,并返回包含该错误类型的最短子数组的长度。
数据结构:
使用 struct ErrorInfo 来记录每种错误类型的频率、首次出现的位置和最后一次出现的位置。
假设错误类型的范围是 [0, 9999],因此定义一个固定大小的数组 errorMap 来存储每种错误类型的信息。
步骤:
遍历输入数组,更新每个错误类型的频率、首次出现位置和最后出现位置。
遍历 errorMap,找到频率最高的错误类型;在频率相等的情况下,选取最短的子数组长度。
结果: 返回包含频率最高的错误类型的最短子数组的长度。
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>#define MAX_ERRORS 10000 // 假设错误类型范围为 [0, 9999]// 定义结构体存储每种错误类型的信息
struct ErrorInfo {int frequency; // 错误类型的出现频率int start; // 错误类型首次出现的位置int end; // 错误类型最后一次出现的位置
};// 函数:计算包含频率最高错误类型的最短子数组长度
int findMinLength(int* errors, int n) {struct ErrorInfo errorMap[MAX_ERRORS] = {0}; // 存储每种错误类型的信息int maxFreq = 0; // 当前最大频率int minLen = INT_MAX; // 当前最短子数组长度// 遍历输入数组,更新错误类型的信息for (int i = 0; i < n; i++) {int error = errors[i];errorMap[error].frequency++; // 增加频率// 如果是该错误类型首次出现,记录起始位置if (errorMap[error].frequency == 1) {errorMap[error].start = i;errorMap[error].end = i;} else {// 更新该错误类型的最后出现位置errorMap[error].end = i;}}// 遍历所有错误类型,找到频率最高的并计算最短子数组长度for (int i = 0; i < MAX_ERRORS; i++) {if (errorMap[i].frequency > 0) { // 仅处理出现过的错误类型int freq = errorMap[i].frequency; // 当前错误类型的频率int length = errorMap[i].end - errorMap[i].start + 1; // 子数组长度// 更新最大频率和最短子数组长度if (freq > maxFreq || (freq == maxFreq && length < minLen)) {maxFreq = freq;minLen = length;}}}return minLen; // 返回结果
}int main() {int n;scanf("%d", &n); // 输入数组长度// 动态分配内存存储错误数组int* errors = (int*)malloc(n * sizeof(int));for (int i = 0; i < n; i++) {scanf("%d", &errors[i]); // 输入错误类型}// 输出包含频率最高错误类型的最短子数组长度printf("%d\n", findMinLength(errors, n));// 释放分配的内存free(errors);return 0;
}
JS解法
-
解题思路
-
目标: 找到数组中出现频率最高的元素,并返回包含该元素的最短子数组的长度。
解题步骤:
记录频率:用 freq 哈希表记录每个元素的出现次数。
记录范围:用 positions 哈希表记录每个元素首次出现的位置和最后一次出现的位置。
计算最短子数组:
遍历 freq,找到频率最高的元素;
如果多个元素的频率相同,选择包含该元素的最短子数组。
最终返回: 返回包含频率最高的元素的最短子数组的长度。
javascript">// 函数:找到包含频率最高元素的最短子数组长度
function getMinSubArray(arr) {const freq = {}; // 哈希表:记录每个元素的出现频率const positions = {}; // 哈希表:记录每个元素的起始和结束位置// 遍历数组,更新频率和范围信息for (let i = 0; i < arr.length; i++) {const num = arr[i];freq[num] = (freq[num] || 0) + 1; // 更新元素的频率// 如果是首次出现,记录起始位置;否则更新结束位置if (!positions[num]) {positions[num] = [i, i];} else {positions[num][1] = i;}}let maxFreq = 0; // 当前最大频率let minLen = Infinity; // 当前最短子数组长度// 遍历频率表,找到频率最高的元素及其最短子数组长度for (const [key, count] of Object.entries(freq)) {const [start, end] = positions[key]; // 获取元素的起始和结束位置const len = end - start + 1; // 子数组长度// 如果当前频率更高,或者频率相等但长度更短,更新结果if (count > maxFreq || (count === maxFreq && len < minLen)) {maxFreq = count;minLen = len;}}return minLen; // 返回最短子数组长度
}// 处理命令行输入
const readline = require("readline");
const rl = readline.createInterface({input: process.stdin,output: process.stdout,
});let lines = []; // 存储输入行
rl.on("line", (line) => {lines.push(line);// 当输入达到两行时,处理数据if (lines.length === 2) {const arr = lines[1].split(" ").map(Number); // 解析数组console.log(getMinSubArray(arr)); // 输出结果lines = []; // 重置输入缓存}
});
注意:
如果发现代码有用例覆盖不到的情况,欢迎反馈!会在第一时间修正,更新。
解题不易,如对您有帮助,欢迎点赞/收藏