使用 std::vector 在 2D 矩阵中搜索元素

Question

bool findInMatrix(int x, vector<vector<int>> &arr)
{
    //    Write your code here.
    for(int i = 0;i<arr.size();i++)
    {
        for(int j = 0;j<arr[0].size();j++)
        {
            if(arr[i][j] == x)
                return true;    
        }
    }
    return false;
}

任何人都可以帮助我解决这个问题，我能够通过所有测试用例，但得到 TLE！

Answer 1

内部for循环似乎有问题。当您应该循环第 i 个向量的大小时，您正在循环第 0 个向量的大小。每个向量可以有不同的大小。

bool findInMatrix(int x, vector<vector<int>> &arr) {

    for(int i = 0; i < arr.size(); i++) {
        for(int j = 0; j < arr[i].size(); j++) {
            if(arr[i][j] == x) {
                return true;    
            }
        }
    }
    return false;
}

Answer 2

可能您需要使用 STL 的 find 这可能是最佳的。

#include <iostream>
#include <vector>
#include <algorithm>

using std::vector,std::find;

bool findInMatrix(int x, vector<vector<int>> &arr)
{
    //    Write your code here.     
    for(auto& rows:arr){    
        auto it = find(rows.begin(), rows.end(), x);
        if (it != rows.end())
        {
            return true;
        }   
    }     
    
    return false;
}


int main(){
    
    vector<vector<int>> arr;
    int rows = 5;
    int cols = 4;

    // init with random data
    for(int i = 0; i<rows;i++){
        vector<int> elems;
         for(int j = 0; j<cols;j++){            
            elems.push_back(rand()%100); 
        }  
        arr.push_back(elems);
    }

    // peek the data
    for(const auto & rows:arr){
        for(const auto &elem:rows ){
            std::cout<<elem<<" ";
        }
        std::cout<<"\n";
    }

    int x = arr[3][2];

    std::cout<<"searching for "<<x<<"\n";
    // search for the element
    std::cout<<findInMatrix(x,arr)<<"\n"; // returns true

    std::cout<<findInMatrix(9999,arr)<<"\n"; // returns false

    return 0;
}