【华为OD-E卷-通信误码 100分（python、java、c++、js、c）】
【华为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解法
- 解题思路：
- 目标： 找到数组中出现频率最高的元素，并返回包含该元素的最短子数组的长度。
解题步骤：
记录频率：用一个哈希表 freq_map 记录每个元素的出现次数。
记录首次出现位置：用一个哈希表 first_pos 记录每个元素第一次出现的索引。
更新最长频率和最短长度：
如果当前元素的频率超过已知的最大频率，则更新最大频率 max_freq 和对应的最短子数组长度 min_len。
如果频率相等，则比较当前子数组长度和已有的最短子数组长度，取较小值。
返回结果： 返回包含频率最高的元素的最短子数组的长度。
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 = freq
min_len = i - first_pos[num] + 1 # 更新最短子数组长度
# 如果频率相等，比较并更新最短子数组长度
elif freq == max_freq:
min_len = min(min_len, i - first_pos[num] + 1)
# 返回最短子数组长度
return min_len
if __name__ == "__main__":
# 输入数组长度
n = int(input())
# 输入数组元素
arr = list(map(int, input().split()))
# 输出包含频率最高元素的最短子数组长度
print(find_min_length(arr))
java解法
- 解题思路
- 目标： 找到数组中出现频率最高的元素，并返回包含该元素的最短子数组的长度。
解题步骤：
记录频率：使用 freqMap 记录每个元素的出现次数。
记录首次出现位置：使用 firstPos 记录每个元素第一次出现的索引。
更新最长频率和最短长度：
如果当前元素的频率超过已知的最大频率，则更新 maxFreq 和对应的最短子数组长度 minLen。
如果频率相等，则比较当前子数组长度和已有的最短子数组长度，取较小值。
最终结果： 返回包含频率最高的元素的最短子数组的长度。
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，找到频率最高的元素；
如果多个元素的频率相同，选择包含该元素的最短子数组。
最终返回： 返回包含频率最高的元素的最短子数组的长度。
// 函数：找到包含频率最高元素的最短子数组长度
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 = []; // 重置输入缓存
}
});
注意：
如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏