(新卷,100分)- 通信误码（Java JS Python）-平芜编程栈

(新卷,100分)- 通信误码（Java & JS & Python）

题目描述

信号传播过程中会出现一些误码，不同的数字表示不同的误码ID，取值范围为1~65535，用一个数组记录误码出现的情况，
每个误码出现的次数代表误码频度，请找出记录中包含频度最高误码的最小子数组长度。

输入描述

误码总数目：取值范围为0~255，取值为0表示没有误码的情况。
误码出现频率数组：误码ID范围为1~65535，数组长度为1~1000。

输出描述

包含频率最高的误码最小子数组长度

用例

输入	5 1 2 2 4 1
输出	2
说明	频度最高的有1和2，频度是2（出现的次数都是2）。可以包含频度最高的记录数组是[2 2]和[1 2 2 4 1]，最短是[2 2]，最小长度为2。

输入	7 1 2 2 4 2 1 1
输出	4
说明	频度最高的是1和2，最短的是[2 2 4 2]

题目解析

简单的排序题。

首先，我们统计出误码数组各个误码的出现过的索引值，假设统计到idxs对象中，属性是误码，属性值是数组，记录误码出现过的索引位置。

然后将idxs对象的所有属性值（各个误码出现过的索引位置数组）拎出来，即Object.values，然后对这些索引位置数组，进行排序，先按照索引位置数组长度进行排序，长度越长，说明频率越高，排序越靠前，如果两个数组长度相同，则看索引跨度，即索引数组的头元素索引和尾元素索引的差距，差距越小，越靠前。这样排序后，得到的首元素数组的首尾索引跨度就是题解。

JavaScript算法源码

/* JavaScript Node ACM模式 控制台输入获取 */ const readline = require("readline"); const rl = readline.createInterface({ input: process.stdin, output: process.stdout, }); const lines = []; rl.on("line", (line) => { lines.push(line); if (lines.length == 1) { const total = lines[0] - 0; if (total == 0) { console.log(0); lines.length = 0; } } if (lines.length === 2) { const arr = lines[1].split(" ").map(Number); console.log(getResult(arr)); lines.length = 0; } }); /** * @param {*} arr 误码出现频率数组 */ function getResult(arr) { const idxs = {}; for (let i = 0; i < arr.length; i++) { const code = arr[i]; idxs[code] ? idxs[code].push(i) : (idxs[code] = [i]); } let maxSize = 0; let minLen = 0; for (let values of Object.values(idxs)) { const size = values.length; const len = values.at(-1) - values.at(0) + 1; if (size > maxSize || (size == maxSize && len < minLen)) { maxSize = size; minLen = len; } } return minLen; }

Java算法源码

import java.util.ArrayList; 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(getResult(arr)); } /** * @param arr 误码出现频率数组 * @return 包含频率最高的误码最小子数组长度 */ public static int getResult(int[] arr) { HashMap<Integer, ArrayList<Integer>> idxs = new HashMap<>(); for (int i = 0; i < arr.length; i++) { Integer code = arr[i]; idxs.putIfAbsent(code, new ArrayList<>()); idxs.get(code).add(i); } int maxSize = 0; int minLen = 0; for (ArrayList<Integer> value : idxs.values()) { int size = value.size(); int len = value.get(value.size() - 1) - value.get(0) + 1; if (size > maxSize || (size == maxSize && len < minLen)) { maxSize = size; minLen = len; } } return minLen; } }

Python算法源码

# 算法入口 def getResult(arr): """ :param total: 误码总数目 :param arr: 误码出现频率数组 :return: 包含频率最高的误码最小子数组长度 """ idxs = {} for i in range(len(arr)): code = arr[i] if idxs.get(code) is None: idxs[code] = [i] else: idxs[code].append(i) maxSize = 0 minLen = 0 for values in idxs.values(): size = len(values) length = values[-1] - values[0] + 1 if size > maxSize or (size == maxSize and length < minLen): maxSize = size minLen = length return minLen # 输入获取 total = int(input()) if total == 0: print(0) else: arr = list(map(int, input().split())) print(getResult(arr))