【华为OD-E卷-34 找数字、找等值元素 （本题有同名题，注意辨别） 100分（python、java、c++、js、c）】

id="article_content" class="article_content clearfix" style="height: 2000px; overflow: hidden;"> id="content_views" class="markdown_views prism-tomorrow-night">

【华为OD-E卷-找数字、找等值元素 （本题有同名题，注意辨别） 100分（python、java、c++、js、c）】

题目

给一个二维数组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 个与其相等的数字

用例

用例一：
输入：
3
5
0 3 5 4 2
2 5 7 8 3
2 5 4 2 4
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
  • 1
  • 2
  • 3
  • 4
  • 5
输出：
[[-1, 4, 2, 3, 3], [1, 1, -1, -1, 4], [1, 1, 2, 3, 2]]
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
  • 1

python解法

  • 解题思路：
  • 问题理解：给定一个二维矩阵 nums，每个元素是一个整数。对于矩阵中的每个元素，我们需要计算该元素到矩阵中所有相同值元素的最短曼哈顿距离（即横向和纵向的距离之和）。对于每个元素，输出它到相同值元素的最短距离。

基本思路：

构建位置表：首先遍历整个矩阵，将每个值的位置存储到一个字典中。键是矩阵中的值，值是该值出现的所有位置。
计算最短距离：对于矩阵中的每个元素，查找所有相同值的位置，计算当前元素与这些位置之间的曼哈顿距离，并更新最小距离。
优化：

我们通过 defaultdict(list) 来存储每个值的所有位置，这样可以避免重复的元素覆盖问题。
对于每个元素，我们遍历所有相同值的位置，计算并更新最短曼哈顿距离。
时间复杂度：

假设矩阵的大小是 rows x cols，遍历一次矩阵来构建位置表的时间复杂度是 O(rows * cols)。
对于每个元素，我们遍历所有相同值的位置，最坏情况下，所有元素值相同时，需要遍历所有位置。因此，最坏时间复杂度是 O((rows * cols)²)。
这种解法虽然直接，但在一些特定情况下（例如值非常分散）可能不够高效。

from collections import defaultdict
import sys

# 计算每个元素到相同值的最近距离
def find_nearest_distances(nums):
    # 获取矩阵的行数和列数
    rows = len(nums)
    cols = len(nums[0])
    
    # 使用defaultdict来存储每个值的位置
    value_positions = defaultdict(list)

    # 记录矩阵中每个值的位置
    for i in range(rows):
        for j in range(cols):
            value_positions[nums[i][j]].append((i, j))

    # 初始化结果矩阵，初始值设为-1
    result = [[-1 for _ in range(cols)] for _ in range(rows)]
    
    # 对于每个元素，计算到相同值的最小曼哈顿距离
    for i in range(rows):
        for j in range(cols):
            value = nums[i][j]  # 当前元素的值
            min_distance = sys.maxsize  # 设置一个极大的初始值作为最小距离

            # 遍历所有相同值的位置，计算当前元素与这些位置的曼哈顿距离
            for x, y in value_positions[value]:
                if (i, j) != (x, y):  # 排除自身
                    distance = abs(i - x) + abs(j - y)  # 计算曼哈顿距离
                    min_distance = min(min_distance, distance)  # 更新最小距离

            # 如果最小距离更新过，设置到结果矩阵中
            if min_distance != sys.maxsize:
                result[i][j] = min_distance

    return result

# 主函数，处理输入输出
if __name__ == "__main__":
    rows = int(input())  # 输入矩阵的行数
    cols = int(input())  # 输入矩阵的列数
    nums = []

    # 输入矩阵的内容
    for _ in range(rows):
        nums.append(list(map(int, input().split())))

    # 计算并输出结果矩阵
    result = find_nearest_distances(nums)
    print(result)

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52

java解法

  • 解题思路
  • 问题理解：

给定一个二维矩阵 grid，我们需要计算矩阵中每个元素到同值元素的最近曼哈顿距离。曼哈顿距离是横向和纵向距离之和。对于每个元素，如果找不到同值元素，则返回 -1。
基本思路：

遍历矩阵：遍历每个元素 grid[i][j]。
查找相同值的位置：对每个元素，遍历整个矩阵，查找所有与该元素值相同且位置不同的元素。
计算曼哈顿距离：对于找到的每个相同值元素，计算其与当前元素的曼哈顿距离，并更新最小距离。
返回结果：如果找到至少一个相同值元素，返回最小曼哈顿距离；如果没有，返回 -1。
时间复杂度：

假设矩阵的大小是 rows x cols。我们需要遍历矩阵中的每个元素，然后对每个元素再遍历整个矩阵，因此时间复杂度是 O((rows * cols)²)。
由于每次都遍历整个矩阵查找相同值元素，这种方法的时间复杂度较高，不适合处理非常大的矩阵。
空间复杂度：

我们使用一个 result 数组来存储每个元素的结果，空间复杂度是 O(rows * cols)。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // 使用Scanner类读取输入
        Scanner sc = new Scanner(System.in);
        
        // 输入矩阵的行数和列数
        int rows = sc.nextInt();
        int cols = sc.nextInt();
        
        // 初始化一个二维数组来存储矩阵
        int[][] grid = new int[rows][cols];

        // 读取矩阵的值
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                grid[i][j] = sc.nextInt(); // 填充矩阵
            }
        }

        // 调用处理方法，输出结果
        System.out.println(process(grid));
    }

    public static String process(int[][] grid) {
        int r = grid.length; // 获取矩阵的行数
        int c = grid[0].length; // 获取矩阵的列数
        
        // 初始化结果矩阵，存储每个位置到相同值元素的最短距离
        int[][] result = new int[r][c];

        // 遍历矩阵中的每个元素
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                int target = grid[i][j]; // 当前元素的值
                int minDist = Integer.MAX_VALUE; // 初始化最小距离为最大值

                // 遍历整个矩阵，查找所有与目标值相同的元素
                for (int x = 0; x < r; x++) {
                    for (int y = 0; y < c; y++) {
                        // 确保当前元素和目标元素位置不同
                        if (grid[x][y] == target && (x != i || y != j)) {
                            // 计算曼哈顿距离，并更新最小距离
                            minDist = Math.min(minDist, Math.abs(i - x) + Math.abs(j - y));
                        }
                    }
                }

                // 如果没有找到相同值元素，设为-1，否则设为最小距离
                result[i][j] = (minDist == Integer.MAX_VALUE) ? -1 : minDist;
            }
        }

        // 返回结果矩阵的字符串表示
        return Arrays.deepToString(result);
    }
}

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

C++解法

给定一个二维矩阵 nums，每个元素是一个整数。我们需要计算每个元素到相同值元素的最小曼哈顿距离。如果某个元素没有其他相同值元素，则其距离为 -1。
曼哈顿距离：对于两个点 (x1, y1) 和 (x2, y2)，曼哈顿距离定义为 abs(x1 - x2) + abs(y1 - y2)，即横向和纵向的距离之和。
解题步骤：

第一步：存储每个元素的位置：
使用 unordered_map（哈希表）存储每个元素的所有位置。键是矩阵中的元素值，值是该元素值出现的位置列表。
第二步：计算每个元素的最小曼哈顿距离：
遍历矩阵中的每个元素，查找该元素在 valuePositions 中的所有位置，并计算曼哈顿距离。找出与当前元素相同值元素的最小距离。
如果当前元素没有相同的元素，则返回 -1。
时间复杂度：

构建 valuePositions 需要遍历整个矩阵，时间复杂度是 O(rows * cols)。
对于每个元素 (i, j)，我们需要遍历 valuePositions 中该值的所有位置，最坏情况下每个元素值都相同，因此时间复杂度为 O((rows * cols)²)。
所以总体时间复杂度是 O((rows * cols)²)，这在处理较大矩阵时可能会较慢。
空间复杂度：

valuePositions 存储了矩阵中所有位置的索引，空间复杂度是 O(rows * cols)，因为每个位置都需要存储。
结果矩阵 result 也占用 O(rows * cols) 的空间。

#include 
#include 
#include 
#include 
#include 
using namespace std;

// 计算每个元素到相同值元素的最小曼哈顿距离
vector<vector<int>> findClosestDistances(vector<vector<int>>& nums, int rows, int cols) {
    // 使用unordered_map来存储每个元素出现的位置，键是元素值，值是该值的位置列表
    unordered_map<int, vector<pair<int, int>>> valuePositions;

    // Step 1: 存储每个数字的位置
    // 遍历矩阵，将每个元素的位置存入valuePositions
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            valuePositions[nums[i][j]].emplace_back(i, j);  // 记录位置
        }
    }

    // Step 2: 计算每个数字的最小曼哈顿距离
    // 初始化结果矩阵，默认每个元素的最短距离为-1
    vector<vector<int>> result(rows, vector<int>(cols, -1));

    // 遍历矩阵中的每个元素
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            int value = nums[i][j];  // 当前元素的值
            int minDistance = INT_MAX;  // 初始化最小距离为最大整数

            // 遍历该值的所有位置，计算曼哈顿距离
            for (const auto& pos : valuePositions[value]) {
                int x = pos.first;  // 获取相同值的位置的行索引
                int y = pos.second; // 获取相同值的位置的列索引

                // 如果位置不等于当前元素位置，则计算距离
                if (x != i || y != j) {
                    int dist = abs(x - i) + abs(y - j);  // 计算曼哈顿距离
                    minDistance = min(minDistance, dist); // 更新最小距离
                }
            }

            // 如果找到了最小距离，则更新结果矩阵
            if (minDistance != INT_MAX) {
                result[i][j] = minDistance;
            }
        }
    }

    // 返回最终的结果矩阵
    return result;
}

int main() {
    // 输入矩阵的行数和列数
    int rows, cols;
    cin >> rows >> cols;

    // 初始化矩阵 nums
    vector<vector<int>> nums(rows, vector<int>(cols));

    // Step 3: 输入二维数组
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            cin >> nums[i][j];  // 输入矩阵的每个元素
        }
    }

    // 调用findClosestDistances计算结果
    vector<vector<int>> result = findClosestDistances(nums, rows, cols);

    // 输出结果
    cout << "[";
    for (int i = 0; i < rows; ++i) {
        cout << "[";
        for (int j = 0; j < cols; ++j) {
            cout << result[i][j];
            if (j != cols - 1) cout << ", ";
        }
        cout << "]";
        if (i != rows - 1) cout << ", ";
    }
    cout << "]" << endl;

    return 0;
}

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

C解法

给定一个二维数组 nums，我们需要计算每个元素到同值元素的最近曼哈顿距离。如果某个元素没有相同值的元素，则返回 -1。
曼哈顿距离：对于两个点 (x1, y1) 和 (x2, y2)，曼哈顿距离的计算方式是 abs(x1 - x2) + abs(y1 - y2)，即横向和纵向的距离之和。
解题步骤：

第一步：读取输入：
读取矩阵的行数 rows 和列数 cols，然后填充矩阵 nums。
第二步：计算每个元素的最近距离：
遍历矩阵中的每个元素 (i, j)。
对于每个元素，遍历整个矩阵查找所有与该元素值相同且位置不同的元素 (x, y)，计算曼哈顿距离并找出最小的距离。
第三步：存储结果并输出：
如果找到了相同值的元素，则将最小距离存储在 result[i][j] 中；如果没有，则存储 -1。
最后输出结果矩阵。
时间复杂度：

时间复杂度：需要遍历矩阵中的每个元素，且对于每个元素，需要再次遍历整个矩阵来查找相同值的元素。最坏情况下，时间复杂度为 O(rows * cols) * O(rows * cols) = O((rows * cols)²)。
空间复杂度：由于需要存储输入矩阵和输出结果矩阵，空间复杂度为 O(rows * cols)。
优化建议：

该解法的时间复杂度较高，对于大矩阵可能会遇到性能瓶颈。可以考虑使用其他方法，例如广度优先搜索（BFS）来优化。

#include 
#include 
#include 

#define MAX_ROWS 100
#define MAX_COLS 100

// 计算整数的绝对值
int abs_val(int a) {
    return a < 0 ? -a : a;
}

int main() {
    int rows, cols;
    int nums[MAX_ROWS][MAX_COLS];  // 输入矩阵
    int result[MAX_ROWS][MAX_COLS]; // 存储结果矩阵

    // Step 1: 读取矩阵的行数和列数
    scanf("%d", &rows);
    scanf("%d", &cols);

    // Step 2: 读取二维数组的每个元素
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            scanf("%d", &nums[i][j]);  // 填充输入矩阵
        }
    }

    // Step 3: 计算每个元素到相同值元素的最小曼哈顿距离
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            int value = nums[i][j];  // 当前元素的值
            int min_distance = INT_MAX;  // 初始化最小距离为最大整数

            // Step 4: 查找与当前值相等的最近元素，遍历整个矩阵
            for (int x = 0; x < rows; x++) {
                for (int y = 0; y < cols; y++) {
                    // 确保不是当前元素自己
                    if ((x != i || y != j) && nums[x][y] == value) {
                        // 计算曼哈顿距离并更新最小距离
                        int distance = abs_val(x - i) + abs_val(y - j);
                        if (distance < min_distance) {
                            min_distance = distance;
                        }
                    }
                }
            }

            // Step 5: 如果没有找到相同值元素，则设置为 -1，否则设置为最小距离
            result[i][j] = (min_distance == INT_MAX) ? -1 : min_distance;
        }
    }

    // Step 6: 输出结果数组，按照指定格式输出
    printf("[");
    for (int i = 0; i < rows; i++) {
        printf("[");
        for (int j = 0; j < cols; j++) {
            printf("%d", result[i][j]);
            if (j < cols - 1) {
                printf(", ");
            }
        }
        printf("]");
        if (i < rows - 1) {
            printf(", ");
        }
    }
    printf("]\n");

    return 0;
}

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

JS解法

具体思路如下：

定义问题：

给定一个整数 n，我们希望通过调整它的二进制表示，找到下一个更大的数字，且新数字的1的个数与 n 相同。
主要步骤：

计算 n 的尾部零和1的数量：
通过右移运算，统计 n 从右侧开始连续的零（c0）和紧接其后的1的数量（c1）。这个过程可以通过连续地右移 n 直到不满足条件。
判断边界情况：
如果 c0 + c1 == 31 或者 c0 + c1 == 0，说明 n 是一个全1的数或全0的数，无法找到更大的数字，直接返回 -1。
找到最小的更大数字：
在 n 的二进制表示中，找到一个合适的位来进行调整，令其变得比 n 大，并且保持相同数量的1。
通过将 n 的某些位置的1变为0，再设置右侧最低的多个0为1来实现这一调整。
关键点：

我们通过 c0 和 c1 确定了需要修改的位置，即确定我们需要操作的比特位。
使用位运算 (| 和 &) 来修改相应的比特

function findNextNumber(n) {
    let temp = n;          // 创建临时变量来操作n
    let c0 = 0, c1 = 0;    // c0表示连续的零的个数，c1表示紧随其后的连续1的个数

    // Step 1: 统计尾部连续的0的个数
    while (((temp & 1) === 0) && (temp !== 0)) {
        c0++;            // 如果当前最低位是0，增加c0
        temp >>= 1;      // 右移一位，继续判断
    }

    // Step 2: 统计尾部连续的1的个数
    while ((temp & 1) === 1) {
        c1++;            // 如果当前最低位是1，增加c1
        temp >>= 1;      // 右移一位，继续判断
    }

    // Step 3: 判断边界情况
    // 如果 c0 + c1 == 31 或者 c0 + c1 == 0，说明无法找到更大的数
    if (c0 + c1 === 31 || c0 + c1 === 0) return -1;

    // Step 4: 计算要修改的位置
    let pos = c0 + c1;      // pos是第一个零的位置，准备变为1
    n |= (1 << pos);         // 在pos位置设置1
    n &= ~((1 << pos) - 1);  // 清除pos后面的所有位
    n |= (1 << (c1 - 1)) - 1; // 在清除后的位置设置c1 - 1个1

    return n;  // 返回修改后的数
}

// 读取输入并处理
const readline = require("readline");
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

// 读取一行输入
rl.on("line", (line) => {
    const n = parseInt(line.trim());  // 读取输入的整数
    console.log(findNextNumber(n));   // 调用findNextNumber函数并输出结果
});

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

注意：

如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏

注：本文转载自blog.csdn.net的CodeClimb的文章"https://blog.csdn.net/CodeClimb/article/details/144772422"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！