全网最全面的华为OD机试真题汇总，100%原题题库，不需要开会员即可查看全部内容，更多考题请查看真题库。
真题库：https://www.yuque.com/codernav.com/od
题目：找数字
知识点：哈希表
时间限制：1s 空间限制：256MB 限定语言：不限
题目描述：
给一个二维数组nums，对于每一个元素num[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个与其相等的数字。
示例1
输入：
3
5
0 3 5 4 2
2 5 7 8 3
2 5 4 2 4
输出：
[[-1, 4, 2, 3, 3], [1, 1, -1, -1, 4], [1, 1, 2, 3, 2]]
解题思路：
将二维数组中的值和坐标转化为map对象。
遍历二维数组中的值，找出其值的所有坐标，求出其中距离最短的值
代码实现一：
package com.codernav.demo.hwod.exam;
import java.util.*;
/**
* @title 找数字
* @Description 给一个二维数组nums，对于每一个元素num[i]，找出距离最近的且值相等的元素，输出横纵坐标差值的绝对值之和，如果没有等值元素，则输出-1。
* @Author 开发者导航
* @website https://codernav.com
* @date 2023/5/13
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[][] nums = new int[n][m];
/**
* 将数字和坐标转化为map
* key：nums数组中的各值
* value：nums数组中的坐标的集合
*/
Map<Integer, List<int[]>> map = new HashMap<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int input = sc.nextInt();
nums[i][j] = input;
int[] ints1 = new int[]{i, j}; //将坐标转化为数组
List<int[]> tempList;
if (map.containsKey(input)) {
tempList = map.get(input);
} else {
tempList = new ArrayList<>();
}
tempList.add(ints1);
map.put(input, tempList);
}
}
List<List<Integer>> resList = new ArrayList<>();
for (int i = 0; i < n; i++) {
List<Integer> list = new ArrayList<>();
for (int j = 0; j < m; j++) {
int num = nums[i][j];
List<int[]> listInts = map.get(num);
if (listInts.size() == 1) { //只有一个坐标，则不存在相等的值
list.add(-1);
continue;
}
int min = Integer.MAX_VALUE; //最小距离
for (int[] intnum : listInts) {
int distance = Math.abs(intnum[0] - i) + Math.abs(intnum[1] - j); //求出距离
if (distance == 0) { //距离为0则跳过
continue;
}
min = Math.min(min, distance);
}
list.add(min);
}
resList.add(list);
}
System.out.println(resList);
}
}
代码实现二：
package com.codernav.demo.hwod.exam;
import java.util.Arrays;
import java.util.Scanner;
/**
* @title 找数字
* @Description 给一个二维数组nums，对于每一个元素num[i]，找出距离最近的且值相等的元素，输出横纵坐标差值的绝对值之和，如果没有等值元素，则输出-1。
* @Author 开发者导航
* @website https://codernav.com
* @date 2023/5/13
*/
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int m = in.nextInt();
int n = in.nextInt();
int[][] map = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
map[i][j] = in.nextInt();
}
}
int[][] ans = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
ans[i][j] = find(map, i, j);
}
}
System.out.println(Arrays.deepToString(ans));
}
private static int find(int[][] map, int i, int j) {
int target = map[i][j];
int ans = Integer.MAX_VALUE;
for (int k = 0; k < map.length; k++) {
for (int l = 0; l < map[0].length; l++) {
if (k == i && l == j) {
continue;
}
if (map[k][l] == target) {
ans = Math.min(ans, Math.abs(i - k) + Math.abs(j - l));
}
}
}
return ans == Integer.MAX_VALUE ? -1 : ans;
}
}
相关文章
