【数据结构和算法】找出叠涂元素

其他系列文章导航

Java基础合集
数据结构与算法合集

设计模式合集

多线程合集

分布式合集

ES合集

文章目录

其他系列文章导航

文章目录

前言

一、题目描述

二、题解

三、代码

四、复杂度分析

前言

这是力扣的2661题，难度为中等，解题方案有很多种，本文讲解我认为最奇妙的一种。

一、题目描述

给你一个下标从 0 开始的整数数组 arr 和一个 m x n 的整数矩阵 mat 。arr 和 mat 都包含范围 [1，m * n] 内的所有整数。

从下标 0 开始遍历 arr 中的每个下标 i ，并将包含整数 arr[i] 的 mat 单元格涂色。

请你找出 arr 中在 mat 的某一行或某一列上都被涂色且下标最小的元素，并返回其下标 i 。

示例 1：

image explanation for example 1

输入：arr = [1,3,4,2], mat = [[1,4],[2,3]]
输出：2
解释：遍历如上图所示，arr[2] 在矩阵中的第一行或第二列上都被涂色。

示例 2：

image explanation for example 2

输入：arr = [2,8,7,4,1,3,5,6,9], mat = [[3,2,5],[1,4,6],[8,7,9]]
输出：3
解释：遍历如上图所示，arr[3] 在矩阵中的第二列上都被涂色。

提示：

m == mat.length
n = mat[i].length
arr.length == m * n
1 <= m, n <= 105
1 <= m * n <= 105
1 <= arr[i], mat[r][c] <= m * n
arr 中的所有整数 互不相同
mat 中的所有整数 互不相同

二、题解

这道题其实是常规哈希表的运用，本题也将用 HashMap 来借题。

算法：

因为 mat 的值各不相同，将用HashMap来存储，以mat[i][j]也就是值为键，[i,j]也就是坐标为值，方便后续快速查询某个值所在位置。
然后创建数组 c1 和 c2 ，分别用来记录某行某列有多少单元格被涂色，如 c1[x] = a 代表第 x 行被涂色单元格数量为 a 个，c2[y] = b 代表第 y 列被涂色单元格数量为 b 个。
接着遍历所有的 arr[i] ，查询到 arr[i] 的所在位置 info 后，更新 c1 和 c2，若某行或某列被完全涂色，返回当前下标。

注意题目的意思是：返回刚好涂完一列或一行的时候的最小数字下标。

三、代码

Java版本：

class Solution {
    public int firstCompleteIndex(int[] arr, int[][] mat) {
        int n = mat.length, m = mat[0].length;
        HashMap<Integer, int[]> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                map.put(mat[i][j], new int[]{i, j});//mat[i][j]性质等于arr[i]
            }
        }
        int[] c1 = new int[n], c2 = new int[m];//c1记录某行单元格涂色情况，c1记录某列单元格涂色情况
        for (int i = 0; i < n * m; i++) {
            int[] info = map.get(arr[i]);//info[0]是行坐标，[info[1]]是列坐标
            if (++c1[info[0]] == m || ++c2[info[1]] == n) {
                return i;//第一个叠涂完成的一定是最小的元素
            }
        }
        return -1;
    }
}

C++版本：

class Solution {
public:
    int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {
        int n = mat.size(), m = mat[0].size();
        unordered_map<int, pair<int, int>> map;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                map[mat[i][j]] = make_pair(i, j);
            }
        }
        vector<int> c1(n), c2(m);
        for (int i = 0; i < n * m; i++) {
            pair<int, int> info = map[arr[i]];
            if (++c1[info.first] == m || ++c2[info.secon] == n) return i;
        }
        return -1; // never
    }
};

Python版本：

class Solution:
    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:
        n, m = len(mat), len(mat[0])
        mapping = {mat[i][j]: (i, j) for i in range(n) for j in range(m)}
        c1, c2 = [0] * n, [0] * m
        for i in range(n * m):
            x, y = mapping[arr[i]]
            c1[x], c2[y] = c1[x] + 1, c2[y] + 1
            if c1[x] == m or c2[y] == n: return i
        return -1  # never