#P3073. 找数字(100分)
-
1000ms
Tried: 131
Accepted: 40
Difficulty: 3
所属公司 :
华为od
找数字(100分)
解题思路
先创建一个二维pair动态数组,记录每个值在哪些位置上,因为题目保证了对于每个数字,最多存在 100 个与其相等的数字,那么nn100,复杂度也是可以的,之后的做法就是遍历矩阵的每一个元素,在嵌套一层循环去遍历数字大小相同位置不同的元素,取最小曼哈顿距离即可,具体实现见代码
代码如下
cpp
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> valueCoordinates[105]; // 存储相同值的位置
int matrix[105][105]; // 输入的二维数组
int result[105][105]; // 输出的结果数组
signed main() {
int rows, cols;
cin >> rows >> cols;
// 输入二维数组,初始化 valueCoordinates 和 result
for (int i = 1; i <= rows; i++) {
for (int j = 1; j <= cols; j++) {
cin >> matrix[i][j];
valueCoordinates[matrix[i][j]].push_back(make_pair(i, j));
result[i][j] = -1; // 初始化为-1
}
}
// 计算每个元素与最近相等元素的最小距离
for (int i = 1; i <= rows; i++) {
for (int j = 1; j <= cols; j++) {
int currentValue = matrix[i][j];
for (auto [x, y] : valueCoordinates[currentValue]) {
// 跳过当前位置自身
if (x == i && y == j) continue;
int distance = abs(x - i) + abs(y - j); // 计算曼哈顿距离
// 更新 result 数组中对应位置的最小距离
if (result[i][j] == -1) {
result[i][j] = distance;
} else {
result[i][j] = min(result[i][j], distance);
}
}
}
}
// 按要求格式输出结果
cout << '[';
for (int i = 1; i <= rows; i++) {
if (i != 1) cout << ", ";
cout << '[';
for (int j = 1; j <= cols; j++) {
if (j != 1) cout << ", ";
cout << result[i][j];
}
cout << ']';
}
cout << ']';
return 0;
}
python
def find_nearest_equal_elements(n, m, nums):
value_coordinates = [[] for _ in range(105)] # 存储相同值的位置
result = [[-1] * (m + 1) for _ in range(n + 1)] # 初始化输出的结果数组
# 输入二维数组,初始化 valueCoordinates
for i in range(1, n + 1):
for j in range(1, m + 1):
value_coordinates[nums[i - 1][j - 1]].append((i, j)) # 使用1-based索引
result[i][j] = -1 # 初始化为-1
# 计算每个元素与最近相等元素的最小距离
for i in range(1, n + 1):
for j in range(1, m + 1):
current_value = nums[i - 1][j - 1]
for x, y in value_coordinates[current_value]:
# 跳过当前位置自身
if x == i and y == j:
continue
distance = abs(x - i) + abs(y - j) # 计算曼哈顿距离
# 更新 result 数组中对应位置的最小距离
if result[i][j] == -1:
result[i][j] = distance
else:
result[i][j] = min(result[i][j], distance)
# 按要求格式输出结果
output = '[' + ', '.join(
'[' + ', '.join(str(result[i][j]) for j in range(1, m + 1)) + ']'
for i in range(1, n + 1)
) + ']'
return output
# 示例输入
n = int(input())
m = int(input())
nums = [list(map(int, input().split())) for _ in range(n)]
# 调用函数并打印结果
print(find_nearest_equal_elements(n, m, nums))
java
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); // 行数
int m = scanner.nextInt(); // 列数
int[][] nums = new int[n + 1][m + 1]; // 输入的二维数组
int[][] result = new int[n + 1][m + 1]; // 输出的结果数组
List<int[]>[] valueCoordinates = new ArrayList[105]; // 存储相同值的位置
for (int i = 0; i < valueCoordinates.length; i++) {
valueCoordinates[i] = new ArrayList<>();
}
// 输入二维数组,初始化 valueCoordinates 和 result
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
nums[i][j] = scanner.nextInt();
valueCoordinates[nums[i][j]].add(new int[]{i, j});
result[i][j] = -1; // 初始化为-1
}
}
// 计算每个元素与最近相等元素的最小距离
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
int currentValue = nums[i][j];
for (int[] coordinate : valueCoordinates[currentValue]) {
int x = coordinate[0];
int y = coordinate[1];
// 跳过当前位置自身
if (x == i && y == j) {
continue;
}
int distance = Math.abs(x - i) + Math.abs(y - j); // 计算曼哈顿距离
// 更新 result 数组中对应位置的最小距离
if (result[i][j] == -1) {
result[i][j] = distance;
} else {
result[i][j] = Math.min(result[i][j], distance);
}
}
}
}
// 按要求格式输出结果
System.out.print("[");
for (int i = 1; i <= n; i++) {
if (i != 1) System.out.print(", ");
System.out.print("[");
for (int j = 1; j <= m; j++) {
if (j != 1) System.out.print(", ");
System.out.print(result[i][j]);
}
System.out.print("]");
}
System.out.print("]");
scanner.close();
}
}
题目内容
给一个二维数组nums,对于每一个元素nums[i],找出距离最近的且值相等的元素,
输出横纵坐标差值的绝对值之和,如果没有等值元素,则输出−1。
例如:
输入数组 nums 为
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
- 对于 nums[0][0]=0,不存在相等的值。
- 对于 nums[0][1]=3,存在一个相等的值,最近的坐标为 nums[1][4],最小距离为 4。
- 对于 nums[0][2]=5,存在两个相等的值,最近的坐标为 nums[1][1],故最小距离为 2。
- ...
- 对于 nums[1][1]=5,存在两个相等的值,最近的坐标为 nums[2][1],故最小距离为1。
- ...
输入描述
输入第一行为二维数组的行
输入第二行为二维数组的列
输入的数字以空格隔开。
输出描述
数组形式返回所有坐标值。
备注
- 针对数组 nums[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]]