首页 > 试题广场 >

矩阵元素查找

[编程题]矩阵元素查找

热度指数：28395 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

已知一个有序矩阵mat，同时给定矩阵的大小n和m以及需要查找的元素x，且矩阵的行和列都是从小到大有序的。设计查找算法返回所查找元素的二元数组，代表该元素的行号和列号(均从零开始)。保证元素互异。

数据范围： $0 \le n,m \le 1000$ ，矩阵中的任何元素满足 $0 < mat_{i,j} \le 1000000$

要求：空间复杂度 $O(1)$ ，时间复杂度 $O(n+m)$

示例1

输入

[[1,2,3],[4,5,6]],2,3,6

输出

[1,2]

示例2

输入

[[1,2,3]],1,3,2

输出

[0,1]

算法知识视频讲解

查看答案及解析

梅洛斯

此题我在百度面试的时候面试官问过，虽然简单我一遍没弄出来，现在思考一下直接可以写出来，真应该刷一下题，悔不当初啊！！！

class Solution {
public:
    vector<int> findElement(vector<vector<int> > mat, int n, int m, int x) {
        // write code here
        vector<int>re;
        if (n==0||m==0)return re;
        int row=0,col=m-1;
        while(row<n&&col>=0)
        {
            if (mat[row][col]<x)row++;
            else if(mat[row][col]>x)col--;
            else 
            {
                re.push_back(row);
                re.push_back(col);
                return re;
            }
        }
        return re;
    }
};

发表于 2020-01-07 21:53:37 回复(1)

Aurora1

class Solution:
    def findElement(self, mat, n, m, x):
        i, j = 0, m - 1
        while not (i >= n or j < 0):
            k = mat[i][j]
            if x < k:
                j -= 1
            elif x > k:
                i += 1
            else:
                return [i, j]

编辑于 2017-03-03 11:06:34 回复(0)

Java

Mono_Chrome

import java.util.*;

public class Solution {
    public int[] findElement(int[][] mat, int n, int m, int x) {
        // write code here
        int i = 0;
        int j = m - 1;
        while (i < n && j >= 0) {
            if (mat[i][j] > x) {
                j--;
            } else if (mat[i][j] < x) {
                i++;
            } else {
                break;
            }
        }
        return new int[] {i, j};
    }
}

发表于 2021-05-29 16:15:27 回复(0)

Java

惠灵顿靖

import java.util.*;
public class Solution {
    public int[] findElement(int[][] mat, int n, int m, int x) {
        //为了个人的阅读方面，令m代表行，n代表列
        int tmp=n;
        n=m;m=tmp;
        int [] res=new int[2];
        //从右上角开始，如果x大于该数，则下移，若小于则右移
        int i=0,j=n-1;
        while(i<m&&j>=0)
            {
                if(x>mat[i][j])i++;
                else if(x<mat[i][j])j--;
                else{
                    res[0]=i;
                    res[1]=j;
                    break;
                }
            }
            return res;
    }
}

发表于 2021-04-15 20:25:02 回复(0)

麻了一

    public int[] findElement(int[][] mat, int n, int m, int x) {
        // write code here
        int row = n - 1;
        int col = 0;
        while (col < m && mat[row][col] < x) {
            col++;
        } 
        if (mat[row][col] < x) {
            return new int[]{-1, -1};
        }
        while (row >= 0 && mat[row][col] > x) {
            row--;
        }
        return new int[]{row, col};
    }

发表于 2021-04-11 18:28:56 回复(0)

肥猿

解题思路：从右上角开始查找，如果小于目标值，则下移，反之，则左移

import java.util.*;

public class Solution {
    public int[] findElement(int[][] mat, int n, int m, int x) {
        // write code here
        //从右上角开始查找
        int[] ans=new int[2];
        for(int i=0;i<n;){
            for(int j=m-1;j>=0;){
                if(mat[i][j]<x) i++;
                else if(mat[i][j]>x) j--;
                else {ans[0]=i;ans[1]=j;return ans;}
            }
        }
        return ans;
    }
}

发表于 2021-03-17 20:34:02 回复(0)

是你的浩哥啊

#双指针解法

class Solution:
def findElement(self, mat, n, m, x):
# write code here
i,j = n-1,0
while i >= 0 and j < m:
if mat[i][j]<x:
j += 1
elif mat[i][j]>x:
i -= 1
else:
return [i,j]

发表于 2021-02-01 16:02:31 回复(0)

JavaScript

别卷啦！

function findElement( mat ,  n ,  m ,  x ) {
    // write code here
    let i = 0 ,j = m-1
    while(i<n&&j>=0){
        if(mat[i][j] == x) return [i,j]
        else if(mat[i][j] > x) {
            j--
        }else{
            i++
        }
    }
    return []
}

发表于 2021-01-12 15:23:08 回复(0)

C/C++

nbgao

class Solution {
public:
    vector<int> findElement(vector<vector<int> > mat, int n, int m, int x) {
        vector<int> v;
        if(n==0 || m==0)
            return v;
        int i=0,j=m-1;
        while(i<n && j>=0){
            if(mat[i][j]==x){
                v.push_back(i);
                v.push_back(j);
                return v;             }else if(mat[i][j]<x)                 i++;             else                 j--;          }         return v;
    }
};

发表于 2019-03-05 11:29:46 回复(0)

C/C++

李珑

//思路和评论做多的答主思路一致
class Solution {
public:
	vector<int> findElement(vector<vector<int> > mat, int n, int m, int x) {
		// write code here
		int row = 0;
		int col = m - 1;
		while (row < n && col >= 0){
			if (mat[row][col] == x)
				return{ row, col };
			else if (mat[row][col] < x)
				row++;
			else
				col--;
		}
		return{ -1, -1 };
	}
};

编辑于 2017-08-07 15:34:43 回复(0)

Cavs

尾部不断缩小的二分查找 class Solution {

	public:


	    vector<int> findElement(vector<vector<int>> mat, intn, intm, intx)


	    {


	        for(inti = 0; i < n; ++i)


	        {


	            if(mat[i][0] <= x && mat[i][m - 1] >= x)


	            {


	                intpos = lower_bound(mat[i].begin(), mat[i].end(), x) - mat[i].begin();


	                if(mat[i][pos] == x) returnvector<int>{i,pos};


	                elsem = pos;


	            }


	        }


	        returnvector<int>{-1, -1};


	    }

};

发表于 2017-06-29 19:01:55 回复(0)

BrainerGao

//从右上角开始，如果x大于mat[row][col],则下移一行；
//如果x小于mat[row][col],则左移动一列
import java.util.*; public class Solution {
    public int[] findElement(int[][] mat, int n, int m, int x) {
        if(mat == null || mat.length != n || mat[0].length != m){
            return null;
        }
        int row = 0, col = m - 1;
        while(row < n && col >= 0){
            if(mat[row][col] == x){
                return new int[]{row, col};
            }else if(mat[row][col] < x){
                row++;
            }else{
                col--;
            }
        }
        return null;
    }
}

发表于 2017-05-21 23:35:52 回复(0)

this_guy

//与剑指offer中第一题一样
import java.util.*;
 
public class Solution {
    public int[] findElement(int[][] mat, int n, int m, int x) {
        // write code here
        if(n==0 || m==0)
            return new int [0];
        int []re=null;
        int x0=0;
        int y0=m-1;
        while(x0<mat.length&&y0>=0){
            if(mat[x0][y0]==x){
                re=new int[2];
                re[0]=x0;
                re[1]=y0;
                break;
            }else if(mat[x0][y0]<x){
              
               x0++;
            }else{
                   y0--;
            }
        }
        if(re==null){
            return new int[0];
        }else{
            return re;
        }
    }
     
  
}

发表于 2016-08-19 16:45:13 回复(0)

Python

Yannyezixin

# -*- coding:utf-8 -*-

class Solution:
    def findElement(self, mat, n, m, x):
        if n < 1 and m < 1:
            return []
        
        i = 0
        j = m - 1
        
        while i < n and j >= 0:
            if mat[i][j] == x:
                return [i, j]
            elif mat[i][j] < x:
                i += 1
            else:
                j -=1
        return []

发表于 2016-08-08 14:55:26 回复(0)

忆水寒

//《剑指offer》里面的题目，思路一样；
class Solution {
public:
    vector<int> findElement(vector<vector<int> > mat, int n, int m, int x) 
    {
        // write code here
        vector<int> vec;
        if(n<=0 ||m<=0) return vec;
        int start=0;
        int end=m-1;
        while(start<n && end>=0)
        {
            if(mat[start][end]==x) 
            {
               vec.push_back(start);
               vec.push_back(end);
               break;
            }
            else if(mat[start][end]<x)
            {
                ++start;
            }
            else if(mat[start][end]>x)
            {
                --end;
            }
        }
        return vec;
    }
};

发表于 2016-08-08 12:08:24 回复(0)

Ron

        // write code here
    	if(mat == null || mat.length != n || mat[0].length != m){
    		return null;
    	}
    	int row = 0, col = mat[0].length-1;
    	while(row <= mat.length-1 && col >= 0){
    		if(mat[row][col] == x){
    			return new int[]{row, col};
    		}else if(mat[row][col] > x){
    			col--;
    		}else{
    			row++;
    		}
    	}
    	return null;
    }

发表于 2016-06-10 15:58:29 回复(0)

牛妹夫

import java.util.*;

public class Solution {
    public int[] findElement(int[][] mat, int n, int m, int x) {
        // write code here
        int i = 0;
        int j = m -1;
        while(i<n && j>=0){
            if(mat[i][j] == x)
                return new int[]{i,j};
            if(mat[i][j] <x){
                i = i + 1;// 行增加
            }else{
                j = j - 1;// 列减少
            }
        }
        return new int[]{-1,-1};
    }
    public int[] findE(int[][] A,int i,int j,int n,int m,int x){
        if(A[i][j] == x)
            return new int[]{i,j};
        if(i<0 ||j<0 ||i>=n ||j>=m)
            return new int[]{-1,-1};
        if(A[i][j] <x)
            return findE(A,i+1,j,n,m,x);
        return findE(A,i,j-1,n,m,x);
    }
}

编辑于 2016-02-24 16:41:56 回复(0)

L0L

vector<int> findElement(vector<vector<int> > mat, int n, int m, int x) {
       int i=0,j=m-1;
       vector<int> ret;
       while(j>=0&&i<=n-1){
       	if(mat[i][j]==x){
       		ret.push_back(i);
       		ret.push_back(j);
       		return ret;
		   }
		   if(mat[i][j]>x)	j--;
		   else i++;	
	   }
	   return ret;
    }

发表于 2015-10-12 18:01:00 回复(0)

念润

思路

从右上角开始，每次将搜索值与右上角的值比较，如果大于右上角的值，则直接去除1行，否则，则去掉1列。如下图显示了查找13的轨迹。首先与右上角15比较，13<15，所以去掉最右1列，然后与11比较，这是13>11，去掉最上面1行…以此类推，最后找到13。算法复杂度O(n)，最坏情况需要2n步，即从右上角开始查找，而要查找的目标值在左下角的时候。

代码

class Solution {
public:
    vector<int> findElement(vector<vector<int> > matrix, int row, int col, int x) {
        vector<int> result;
        if(row == 0 || col == 0){
            return result;
        }//if
        int i = 0,j = col - 1;
        while(i < row && j >= 0){
            // 大于目标 剔除这个数字所在的列
            if(matrix[i][j] > x){
                --j;
            }//if
            // 小于目标 剔除这个数字所在的行
            else if(matrix[i][j] < x){
                ++i;
            }//else
            else{
                result.push_back(i);
                result.push_back(j);
                return result;
            }//else
        }//while
        return result;
    }
};

发表于 2015-08-19 13:01:52 回复(0)

阿狸不是猫

import java.util.*;
/*
思路：这题目的意思应该是从第一列第一个到最后一列最后一个都是有序的，不然如果只是单行有序的话就要麻烦很多了
可以分析最右上角的元素，如果这个元素大于所查找的，那必然在最右上角元素的左边即列-1，如果小于，行+1
我本来想递归的，但是从右上角开始做递归要新建一个函数，还要设置约束条件- -贼麻烦
*/
public class Solution {

    public int[] findElement(int[][] mat, int n, int m, int x) {
        int i=0;
        int j=m-1;
		int[] goal=new int[2];
        while(i<n&&j>=0){
            if(mat[i][j]==x){
                goal[0]=i;
        		goal[1]=j;
                break;
            } 
			else if(mat[i][j]>x) j--;
            else i++;
        }
        return goal;
    }
}
运行时间：208ms
占用内存：15224k

发表于 2017-06-30 15:12:21 回复(0)