首页 > 试题广场 >

矩阵查数

[编程题]矩阵查数

热度指数：5515 时间限制：C/C++ 4秒，其他语言8秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

给定一个二维整型矩阵，已知矩阵的每一行都按照从小到大的顺序排列，每一列也都按照从小到大的顺序排列。现在给出一个数，请写一个函数返回该数是否存在于矩阵中。

矩阵中出现的数字与需要查找的数(k)都为0~100000之间的整数，且矩阵的大小在3000*3000以内。

在保证正确性的基础上，请尽量给出比较高效的解法。请列出你的算法时间复杂度与空间复杂度分别是多少？

输入描述:

输入两个整数m,n, 且 0<m<=3000, 0<n<=3000。

接着输入一个vector<vector<int>> matrix矩阵，大小为m行n列，与一个int k，为需要查找的数字。

输出描述:

输出true或者false，true表示该数k存在于该matrix矩阵中，false表示该数k不存在于该matrix矩阵中。

示例1

输入

输出

true

说明

4位于矩阵的第二行第二列，故输出true

算法知识视频讲解

C/C++

nbgao


	
	
		#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,m,x;
    bool M[100001];
    cin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++){
            cin>>x;
            M[x] = true;
        }
    cin>>x;
    if(!M[x])
        cout<<"false"<<endl;
    else
        cout<<"true"<<endl;
    return 0;
}

发表于 2019-07-23 20:41:05 回复(2)

C/C++

ElonB

/*
从左下(或右上)开始遍历，
相等则找到，小于则向右遍历，大于则向上遍历。
时间复杂度O(m+n)，空间复杂度O(m*n)
*/
#include<bits/stdc++.h>
using namespace std;

int main()
{
//    freopen("input.txt", "r", stdin);
    int m, n, x, i, j, k;
    cin >> m >> n;
    vector<vector<int>> matrix;
    for(i = 0; i < m; i++) {
        vector<int> temp;
        for(j = 0; j < n; j++) {
            cin >> x;
            temp.push_back(x);
        }
        matrix.push_back(temp);
    }
    cin >> k;

    i = m - 1;
    j = 0;
    bool flag = false;
    while(i >= 0 && j < n) {
        if(matrix[i][j] == k) {
            flag = true;
            break;
        } else if(matrix[i][j] < k) j++;
        else i--;
    }
    if(flag) cout << "true" << endl;
    else cout << "false" << endl;
    return 0;
}

/*
以空间换时间
查找过程，时间复杂度O(1)，空间复杂度O(N)
*/
#include<bits/stdc++.h>
using namespace std;
#define N 100001
bool a[N];

int main()
{
//    freopen("input.txt", "r", stdin);
    int m, n, x, i, j, k;
    memset(a, 0, sizeof(a));
    scanf("%d%d", &m, &n);
    for(i = 0; i < m * n; i++) {
        scanf("%d", &x);
        a[x] = true;
    }
    scanf("%d", &k);

    if(a[k]) printf("true\n");
    else printf("false\n");
    return 0;
}

编辑于 2019-07-13 12:53:04 回复(0)

pein531

从右上开始搜索，如果比目标大，则向左搜索；比目标小则向下搜索，时间复杂度为O(m + n)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.lang.String;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String strMN;
        while((strMN = br.readLine()) != null) {
            String[] mn = strMN.split(" ");
            int m = Integer.parseInt(mn[0]);
            int n = Integer.parseInt(mn[1]);
            int[][] matrix = new int[m][n];
            for(int i = 0; i < m; i++){
                String[] strRow = br.readLine().trim().split(" ");
                for(int j = 0; j < n; j++)
                    matrix[i][j] = Integer.parseInt(strRow[j]);
            }
            int target = Integer.parseInt(br.readLine().trim());
            System.out.println(search(matrix, target));
        }
    }
    
    private static boolean search(int[][] arr, int k) {
        int row = arr.length, col = arr[0].length;
        int rowStart = 0, colStart = col - 1;
        while(rowStart < row && colStart >= 0){
            if(arr[rowStart][colStart] > k) {
                colStart --;
            }else if(arr[rowStart][colStart] < k){
                rowStart ++;
            }else{
                return true;
            }
        }
        return false;
    }
}

发表于 2020-10-28 19:59:27 回复(0)

C_AleXPump

读数据的时候用set,找的时候直接o(1)复杂度找出。关于set插入的复杂度参见https://wiki.python.org/moin/TimeComplexity。插s1,s2...sn的复杂度为(n-1)*O(l) where l is max(len(s1),..,len(sn))。数字的长度远远小于log(m+n)

size = input()
m,n = size.split()
m = int(m)
mySet = set() for i in range(m):
    newLine = input()
    nums = newLine.split()  for num in nums:
        mySet.add(num)
target = input() print ("true") if target in mySet else print ("false")

注意输出是 true 不是True，所以不能直接打印python的布尔值

编辑于 2019-02-23 12:17:16 回复(7)

Java

京东内推君

利用有序性，从左上角或者右下角开始查找

代码为从左上角

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int row = scanner.nextInt();
        int column = scanner.nextInt();
        int[][] value = new int[row][column];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                value[i][j] = scanner.nextInt();
            }
        }
        int aim = scanner.nextInt();

        int curR = 0;
        int curC = column - 1;
        boolean flag = false;
        while (curR >= 0 && curR < row && curC >= 0 && curC < column) {
            if (value[curR][curC] > aim) {
                curC--;
            } else if (value[curR][curC] < aim) {
                curR++;
            } else {
                flag = true;
                break;
            }
        }
        System.out.println(flag);
    }
}

发表于 2020-06-23 20:18:55 回复(0)

Java

何止hz

时间都浪费在读取数据上了。。。。。。。

发表于 2020-05-03 22:17:48 回复(0)

小小呆萌坤

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

//总结目前牛客问题 第一,没有循环输入问题, 第二 有循环输入问题, 第三 输入有多余空格问题 ,第四 中间插入多余空行问题 ....
namespace Test0001
{
    class Program
    {
        public static void Main(string[] args)
        {
            //string line;
            //while (!string.IsNullOrEmpty(line = Console.ReadLine())) Func(line);
            Func(Console.ReadLine());
        }
        public static void Func(string line)
        {
            var s1 = line.Trim().Split(' ').Select(x => int.Parse(x)).ToArray();
            int n = s1[0], m = s1[1];
            int[,] mir = new int[n, m];

            for (int j = 0; j < m; j++)
            {
                var s2 = Console.ReadLine().Trim().Split(' ').Select(x => int.Parse(x)).ToArray();
                for (int i = 0; i < n; i++)
                {
                    mir[i, j] = s2[i];
                }
            }

            int key = int.Parse(Console.ReadLine());

            int s = 0, e = n - 1;
            while (s<e)
            {
                int mid = (s + e) / 2;
                int val = mir[mid, 0];
                if (e - s == 1) break;
                if (val > key)
                {
                    e = mid;
                }
                else if(val == key)
                {
                    Console.WriteLine("true");
                    return;
                }
                else
                {
                    s = mid;
                }
            }
            //起点 (s,0)
            Console.WriteLine(Find(s, 0, m, mir, key).ToString().ToLower()); 
        }
       
        //比key 大 往左遍历, 比 key小 往下 遍历
        public static bool Find(int x, int y, int m, int[,] mir, int key)
        {
            if (x < 0 || y >= m) return false;
            if (mir[x, y] > key)
            {
                return Find(x - 1, y, m, mir, key);
            }
            else if( mir[x,y] == key)
            {
                return true;
            }
            else
            {
                return Find(x, y + 1, m, mir, key);
            }
        }
    }
}

根据矩阵的特殊性,从右上或者左下开始遍历寻找皆可,我这里是使用右上角开始,首先二分法快速找到起点之后用找到的数和Key值比较如果大了x-- 如果小了 y++ 直到找到为止,最坏情况 m+n次

发表于 2019-12-11 16:23:40 回复(0)

嘻嘻啧啧

提供一个Java的合理输入

import java.util.Scanner;
public class Main
{
public static boolean search(int[][] matrix,int target)
{
int n_row=matrix.length,n_col=matrix[0].length;
int i=0,j=n_col-1;
while(i<n_row && j>=0)
{
if(matrix[i][j]>target)
j--;
else if(matrix[i][j]<target)
i++;
else
return true;
}
return false;
}

public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
int[][] matrix=null;
int a=0,b=0;

a = in.nextInt();
b = in.nextInt();
matrix=new int[a][b];

for(int i=0;i<a;i++)
{
for(int j=0;j<b;j++)
{
matrix[i][j]=in.nextInt();
}
}

int target=in.nextInt();
System.out.println(search(matrix,target));

}
}

发表于 2019-03-08 17:14:47 回复(0)

牛客497864927号

从左下角开始搜索，若目标值大于当前位置的值，则向右，否则向上。

#include <cstdio>
#include <vector>
using namespace std;

int main()
{
    int m, n, target;
    scanf("%d%d", &m, &n);
    vector<vector<int> > matrix(m, vector<int>(n));
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            scanf("%d", &matrix[i][j]);
    scanf("%d", &target);
    int px = 0, py = m-1;
    bool found = false;
    while (px < n && py > 0 && !found)
    {
        if (matrix[py][px] == target) 
            found = true;
        else if (matrix[py][px] < target)
            px++;
        else 
            py--;
    }
    printf("%s\n", found?"true":"false");

    return 0;
}

发表于 2021-01-12 14:24:14 回复(0)

永不秃头

用例通过率: 100.00% 运行时间: 1963ms 占用内存: 52064KB

#include<iostream>

#include<vector>

using namespace std;

int main()
{
    int n,m,k;
    
    cin>>m>>n;
    vector<vector<int>> arr(m,vector<int>(n));
    for(int i=0;i<m;i++)
        for(int j=0;j<n;j++)
            cin>>arr[i][j];
    cin>>k;
    int i=m-1;
    int j=0;
    while(i>=0&&j<n)
    {
       if(arr[i][j]>k)
          i--;
       else if(arr[i][j]<k)
          j++;
            
       else if(arr[i][j]==k)
       {
           cout<<"true";
           return 0;
        }
     }
    cout<<"false";
    
    return 0;
}

发表于 2020-08-14 14:00:32 回复(0)

橘子汽水超人2号

输入输出弄到崩溃啊

这什么输入输出啊，非常不适应啊....

# -*- coding:utf-8 -8-
import sys
def main():
    lines = sys.stdin.readlines()
    num=lines[-1].strip()
    for line in lines[1:-1]:
        tmp = line.strip().split()
        if num in tmp:return 'true'
    return 'false'
if __name__=='__main__':
    print(main())

编辑于 2020-06-08 23:19:20 回复(0)

情谊X如歌

A了80%，但是不知道问题在哪里。

说一下思路吧，首先使用二分法找到比target大的最小值和比target小的最大值，那么target的范围就在这几行元素之中了，然后遍历这几行，使用二分法查找target，找到就返回true，如果遍历完仍然没有找到target，就返回false。

import java.util.*;
public class Main {
    public boolean is_in_matrix(){
        Scanner sc = new Scanner(System.in);
        String[] s = sc.nextLine().split(" ");
        int n = Integer.parseInt(s[0]);
        int m = Integer.parseInt(s[1]);
        if(n==0) return false;
        ArrayList<int[]> arr = new ArrayList<>();
        for(int i = 0; i<n;i++){
            String string = sc.nextLine();
            string = string.trim();
            String[] chars = string.split(" ");
            int [] mat = new int[m];
            for(int j = 0; j<m;j++){
                mat[j] = Integer.parseInt(chars[j]);
            }
            arr.add(mat);
        }
        int target = sc.nextInt();
        int []row_elm = new int[n];
        for(int i = 0;i<n;i++){
            row_elm[i] = arr.get(i)[0];
        }
        //scan存储比target小的最大值行和比target大的最小值行
        int[] scan = find_target(row_elm, target);
        return find_targetnum(arr,scan,target);
    }
    
    //使用二分查找搜索target
    private boolean find_targetnum(ArrayList<int[]> arr,int [] scan, int target) {
        //遍历scan中的几行元素，查看target是否在其中
        for(int i = scan[0];i<=scan[1];i++){
            int[] arrs = arr.get(i);
            int low = 0,high = arrs.length-1;
            while (low<=high){
                int mid = (high+low)/2;
                if(arrs[mid]==target){
                    return true;
                }
                else if(arrs[mid]<target){
                    low = mid+1;
                }
                else {
                    high=mid-1;
                }
            }
        }
        return false;
    }  private int [] find_target(int[] row_elm,int target) {
        //求小于等于target的最大值
        int [] scan= new int[2];
        int i = 0;
        int j = row_elm.length-1;
        while (i<j){
            int mid = (i+j+1)/2;
            if(row_elm[mid]<=target){
                i=mid;
            }
            else {
                j=mid-1;
            }
        }

        //求大于等于target的最小值
        int low = 0 ,high = row_elm.length-1;
        while (low<high){
            int mid = (low+high)/2;
            if(row_elm[mid]>=target){
                high=mid;
            }
            else {
                low= mid+1;
            }
        }
        scan[0] = j;
        scan[1] = low;
        return scan;
    }

    public static void main(String[] args) {
        System.out.println(new Main().is_in_matrix());
    }
}

编辑于 2020-05-29 15:45:39 回复(0)

C/C++

旷视内推君

#include <iostream>
(720)#include <vector>
using namespace std;
int main()
{
    int m, n;
    cin >> m >> n;
    vector<vector<int>> nums(m, vector<int>(n));
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> nums[i][j];
        }
    }
    int k;
    cin >> k;
    int i = m - 1, j = 0;
    while (i >= 0 && j < n)
    {
        int y = nums[i][j];
        if (y == k)
        {
            cout << "true";
            return 0;
        }
        if (y < k)
            j++;
        else
            i--;
    }
    cout << "false";
    return 0;
}

发表于 2020-04-15 08:59:41 回复(0)

牛客713170399号

这题我也是醉了，常用的解法说我超内存，倒是最垃圾的解法过了：）

def main2():
    m, n = map(int, input().split())
    k = []
    for i in range(m):
        k.append(list(map(int, input().split())))
    t = int(input())
    i = 0
    j = n-1
    while i < m and j < n:
        if k[i][j] == t:
            return True
        elif k[i][j] > t:
            j -= 1
        else:
            i += 1
    return False


def main():
    m, n = map(int, input().split())
    k = []
    for i in range(m):
        k.append(input())
    t = input()
    i = 0
    while i < m:
        if t in k[i]:
            return True
        i += 1
    return False


if __name__ == "__main__":
    if main():
        print("true")
    else:
        print("false")

编辑于 2020-04-13 18:31:20 回复(0)

初心者托奇

老老实实用字典

d = {}
for i in range(int(input().split()[0])):
    d.update({j:'true' for j in input().split()})
try:
    print(d[input()])
except:
    print('false')

发表于 2020-03-16 15:51:29 回复(0)

炳烛

try:
ss=input().split()
hang=int(ss[0])
lie=int(ss[1])
li=set()
for i in range(hang):
a=set(input().split())
li=li|a
c=input()

if c in li:
print('true')
else:
print('false')
except:
print('!')

发表于 2020-02-19 04:36:58 回复(0)

Python

这题太难了

这都能过。。。。。

def main():
    # nlogn
    m, n = list(map(int, input().strip().split()))
    dict = {}
    for i in range(m):
        for j in input().split():
            if j not in dict:
                dict[j] = 1
    k = input()
    print('true') if k in dict else print('false')
if __name__ == '__main__':
    main()

发表于 2020-02-18 17:40:11 回复(0)

C/C++

Shopee内推小虾米

#include <bits/stdc++.h>
using namespace std;
 
const int max_mn = 3001;
int V[max_mn][max_mn];
// =36MB
int main(){
    int m,n;
    cin>>m>>n;
    //memset(V,0,sizeof(V));
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            scanf("%d",&V[i][j]);
            //cin>>V[i][j];
        }
    }
    int k;
    cin>>k;
     
    bool ans=false;
    //从右上角开始判定
    int i=0,j=n-1;
    while(i<m and j>=0){
        if(V[i][j]==k){
            ans = true;
            break;
        }
        if(V[i][j]<k){//第i行pass掉
            i=i+1;
        }else{//第j列被pass掉
            j=j-1;
        }
    }
    if(ans) cout<<"true"<<endl;
    else cout<<"false"<<endl;
     
    return 0;
}

O(2*n)时间复杂度 O(n^2)的空间复杂度

发表于 2020-02-17 19:37:27 回复(0)