刷题笔记合集🔗

找数字-找等值元素

问题描述

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

输入格式

第一行输入两个整数 和 ，分别表示二维数组的行数和列数。

接下来 行，每行包含 个整数，表示二维数组 的元素，相邻两个整数之间用空格分隔。

输出格式

输出一个二维数组，其中每个元素表示对应位置的结果。

样例输入1

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

样例输出1

[[-1, 4, 2, 3, 3], [1, 1, -1, -1, 4], [1, 1, 2, 3, 2]]

样例解释

数据范围

题解

这道题目要求我们找出每个元素最近的相等元素，并计算距离。解决这个问题的关键在于如何高效地找到相等的元素并计算距离。

一个直观的思路是，对于每个元素，遍历整个数组寻找相等的元素并计算距离。但这种方法的时间复杂度是 ，对于较大的输入会超时。

我们可以采用一种更高效的方法：

1. 首先，遍历整个数组，用一个哈希表记录每个数值出现的所有位置。
2. 然后，再次遍历数组，对于每个元素，在哈希表中找到所有相等的元素位置，计算距离并取最小值。

这种方法的时间复杂度是 ，其中 是每个数值平均出现的次数。在最坏情况下， 可能接近 ，但在实际情况中， 通常远小于 。

参考代码

• Python

from collections import defaultdict
from typing import List

def find_nearest_equal(nums: List[List[int]]) -> List[List[int]]:
    # 获取矩阵的行数和列数
    n, m = len(nums), len(nums[0])
    
    # 创建一个默认字典，用于存储每个数值出现的位置
    positions = defaultdict(list)
    
    # 遍历矩阵，记录每个数值出现的位置
    for i in range(n):
        for j in range(m):
            positions[nums[i][j]].append((i, j))
    
    # 创建结果矩阵，初始化为-1
    result = [[-1] * m for _ in range(n)]
    
    # 再次遍历矩阵，计算每个元素到最近相等元素的距离
    for i in range(n):
        for j in range(m):
            # 获取当前元素值对应的所有位置
            pos_list = positions[nums[i][j]]
            
            # 如果只有一个位置（当前位置），则保持-1
            if len(pos_list) == 1:
                continue
            
            # 计算到其他相等元素的最小距离
            min_dist = float('inf')
            for x, y in pos_list:
                if x != i or y != j:  # 不与自身比较
                    dist = abs(x - i) + abs(y - j)
                    min_dist = min(min_dist, dist)
            
            # 更新结果矩阵
            result[i][j] = min_dist
    
    return result

# 读取输入
n = int(input())
m = int(input())
nums = [list(map(int, input().split())) for _ in range(n)]

# 计算结果并输出
result = find_nearest_equal(nums)
print(result)

• C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define MAX_N 1000
#define MAX_M 1000

// 定义位置结构体
typedef struct {
    int x, y;
} Position;

// 定义哈希表节点
typedef struct Node {
    int key;
    Position* positions;
    int count;
    int capacity;
    struct Node* next;
} Node;

// 定义哈希表
typedef struct {
    Node* table[10007];
} HashMap;

// 初始化哈希表
void initHashMap(HashMap* map) {
    memset(map->table, 0, sizeof(map->table));
}

// 哈希函数
int hash(int key) {
    return abs(key) % 10007;
}

// 在哈希表中插入元素
void insert(HashMap* map, int key, int x, int y) {
    int index = hash(key);
    Node* node = map->table[index];
    while (node) {
        if (node->key == key) {
            if (node->count == node->capacity) {
                node->capacity *= 2;
                node->positions = realloc(node->positions, node->capacity * sizeof(Position));
            }
            node->positions[node->count].x = x;
            node->positions[node->count].y = y;
            node->count++;
            return;
        }
        node = node->next;
    }
    node = malloc(sizeof(Node));
    node->key = key;
    node->capacity = 4;
    node->positions = malloc(node->capacity * sizeof(Position));
    node->positions[0].x = x;
    node->positions[0].y = y;
    node->count = 1;
    node->next = map->table[index];
    map->table[index] = node;
}

// 在哈希表中查找元素
Node* find(HashMap* map, int key) {
    int index = hash(key);
    Node* node = map->table[index];
    while (node) {
        if (node->key == key) {
            return node;
        }
        node = node->next;
    }
    return NULL;
}

// 计算最近相等元素的距离
int** findNearestEqual(int** nums, int n, int m) {
    HashMap map;
    initHashMap(&map);

    // 记录每个数值出现的位置
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            insert(&map, nums[i][j], i, j);
        }
    }

    // 创建结果数组
    int** result = malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        result[i] = malloc(m * sizeof(int));
        memset(result[i], -1, m * sizeof(int));
    }

    // 计算每个元素到最近相等元素的距离
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            Node* node = find(&map, nums[i][j]);
            if (node->count > 1) {
                int minDist = INT_MAX;
                for (int k = 0; k < node->count; k++) {
                    if (node->positions[k].x != i || node->positions[k].y != j) {