leetcode刷题记录——2023年12月

Andromeda

发布于 2023-12-02 12:22:55

1510

发布于 2023-12-02 12:22:55

文章被收录于专栏：Andromeda的专栏

2661、找出叠涂元素——哈希表

超时方法

首先，通过使用unordered_map来构建矩阵mat中元素与其索引的映射关系。遍历矩阵中的每个元素，将元素作为键，将其索引{i, j, 0}作为值，存储在matrix中。这样做的目的是方便后续根据元素值查找对应的索引。

接下来，遍历数组arr中的每个数，依次进行以下操作：

将当前数在matrix中对应索引的第三个元素置为1，表示该数已经在数组arr中出现过。
初始化一个标志变量flag为1，用于标记当前数所在行或列的所有数是否都在数组arr中出现过。
获取当前数在matrix中对应的索引的行号y_pos和列号x_pos。
遍历当前数所在行的所有数，如果有任何一个数在matrix中对应索引的第三个元素不等于1（即未在数组arr中出现过），则将flag置为0，并跳出循环。
如果flag仍然为1，说明当前数所在行的所有数都在数组arr中出现过，返回当前数的索引。
如果flag为0，继续下一步操作。
将flag重新置为1。
遍历当前数所在列的所有数，如果有任何一个数在matrix中对应索引的第三个元素不等于1（即未在数组arr中出现过），则将flag置为0，并跳出循环。
如果flag仍然为1，说明当前数所在列的所有数都在数组arr中出现过，返回当前数的索引。
如果flag为0，继续下一次循环。

class Solution {
public:
    int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) {
        unordered_map<int, vector<int>> matrix;
        for(int i=0;i<mat.size();i++){
            for(int j=0;j<mat[0].size();j++){
                matrix[mat[i][j]] = {i, j, 0};
            }
        }
        for(int i=0;i<arr.size();i++){
            matrix[arr[i]][2] = 1;
            int flag = 1;
            int y_pos = matrix[arr[i]][0];
            int x_pos = matrix[arr[i]][1];
            for(int x=0;x<mat[0].size();x++){
                if(matrix[mat[y_pos][x]][2] == 0){
                    flag = 0;
                    break;
                }
            }
            if(flag == 1){
                return i;
            }
            flag = 1;
            for(int y=0;y<mat.size();y++){
                if(matrix[mat[y][x_pos]][2] == 0){
                    flag = 0;
                    break;
                }
            }
            if(flag == 1){
                return i;
            }else{
                continue;
            }
        }
        return 0;
    }
};

优化

将刚刚遍历 arr[i] 的行和列改为用哈希表存储行和列的被涂色的元素个数，每次涂色更新并检查该元素的行列中被涂色的元素个数，如果满一行或者一列，则返回 arr 的当前下标。

class Solution
{
public:
    int firstCompleteIndex(vector<int> &arr, vector<vector<int>> &mat)
    {
        int h = mat.size();
        int w = mat[0].size();
        unordered_map<int, pair<int, int>> matrix;
        unordered_map<int, int> row;
        unordered_map<int, int> col;
        for (int i = 0; i < h; i++)
        {
            row[i] = 0;
            for (int j = 0; j < w; j++)
            {
                col[j] = 0;
                matrix[mat[i][j]] = {i, j};
            }
        }
        for (int i = 0; i < h * w; i++)
        {
            int x_pos = matrix[arr[i]].second;
            col[x_pos]++;
            if (col[x_pos] == h)
            {
                return i;
            }
            int y_pos = matrix[arr[i]].first;
            row[y_pos]++;
            if (row[y_pos] == w)
            {
                return i;
            }
        }
        return 0;
    }
};

------本页内容已结束，喜欢请分享------

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

int