当前位置：首页 > news >正文

华为OD机试 - 找等值元素（Java 2024 E卷 100分）

news 2025/5/11 5:15:15

在这里插入图片描述

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

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（E卷+D卷+A卷+B卷+C卷）》。

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

一、题目描述

给一个二维数组nums，对于每一个元素nums[i]，找出距离最近的且值相等的元素，输出横纵坐标差值的绝对值之和，如果没有等值元素，则输出-1。

例如

输入数组nums为

0 3 5 4 2
2 5 7 8 3
2 5 4 2 4

对于 num[0][0]= 0，不存在相等的值；
对于 num[0][1] = 3，存在一个相等的值，最近的坐标为num[1][4]，最小距离为4；
对于 num[0][2]= 5，存在两个相等的值，最近的坐标为num[1][1]，故最小距离为2；
…
对于num[1][1]= 5，存在两个相等的值，最近的坐标为num[2][1]，故最小距离为1；
…

输出

-1 4 2 3 3
1 1 -1 -1 4
1 1 2 3 2

二、输入描述

输入第一行为二维数组的行
输入第二行为二维数组的列
输入的数字以空格隔开

三、输出描述

数组形式返回所有坐标值。

四、补充说明

针对数组num[i][j]，满足0<i<=100;0<j<=100；
对于每个数字，最多存在100个与其相等的数字；

五、解题思路

首先，根据输入的行数和列数创建一个二维数组 doubleArr；
将输入的数字填充到二维数组中；
创建一个HashMap map，用于统计数组中相同数字的位置；Key为数字，Value为对应数字的坐标数组；
遍历二维数组，对于每一个元素，找出与其相等的其他元素的最小距离；
- 初始化最小距离为最大整数；
- 对于当前元素的数字，通过HashMap map 获取所有相等的数字的坐标数组；
- 遍历相等数字的坐标数组，计算当前元素与其他相等元素的距离，并更新最小距离；
- 将最小距离存储到当前元素的位置；
将二维数组转换为字符串形式，并返回作为结果；

六、Java算法源码

public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();int[][] doubleArr = new int[n][m];// 将数组放入二维数组中for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {doubleArr[i][j] = sc.nextInt();}}System.out.println(get(doubleArr, n, m));
}public static String get(int[][] doubleArr, int n, int m) {// 统计输入矩阵中，相同数字的位置Map<Integer, ArrayList<Integer[]>> map = new HashMap<Integer, ArrayList<Integer[]>>();for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {Integer num = doubleArr[i][j];Integer[] arr = {i, j};map.putIfAbsent(num, new ArrayList<>());map.get(num).add(arr);}}// 遍历矩阵每一个元素，和其他相同数字的位置求距离，取最小距离for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {int num = doubleArr[i][j];int min = Integer.MAX_VALUE;for (Integer[] arr : map.get(num)) {int a = arr[0];int b = arr[1];// 求最小距离if (a != i || b != j) {int temp = Math.abs(a - i) + Math.abs(b - j);min = Math.min(min, temp);}}doubleArr[i][j] = min == Integer.MAX_VALUE ? -1 : min;}}return Arrays.toString(Arrays.stream(doubleArr).map(Arrays::toString).toArray(String[]::new));
}