当前位置: 代码迷 >> 综合 >> 矩阵元素查找
  详细解决方案

矩阵元素查找

热度:50   发布时间:2024-01-16 12:18:06.0

DESC:

题目描述

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

示例1

输入

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

返回值

[1,2]

 

CODE:

JAVA:

import java.util.*;public class Finder {public int[] findElement(int[][] mat, int n, int m, int x) {// write code hereint i = n-1, j = 0;while (mat[i][j] != x) {if (mat[i][j] > x) {i--;} else {j++;}}return new int[]{i,j};}
}

 

 

NOTES:

  1. 前提条件:行列都是有序递增的;
  2. 从第一列由下至上遍历,与目标值对比,小于则排除一行数据,大于则可确定原素再该行,然后再从左至右查找目标值即可,最多(m+n)次比较即可找到;

 

DESC2:

题目描述

请写出一个高效的在m*n矩阵中判断目标值是否存在的算法,矩阵具有如下特征:

每一行的数字都从左到右排序

每一行的第一个数字都比上一行最后一个数字大

例如:

对于下面的矩阵:

[[1,   3,  5,  9],[10, 11, 12, 30],[230, 300, 350, 500]
]

要搜索的目标值为3,返回true;

示例1

输入

[[1,3,5,9],[10,11,12,30],[230, 300, 350, 500]],3

返回值

true

 

CODE2:

JAVA:

import java.util.*;public class Solution {/*** * @param matrix int整型二维数组 * @param target int整型 * @return bool布尔型*/public boolean searchMatrix (int[][] matrix, int target) {// write code hereif (matrix == null || matrix.length==0) {return false;}int m = matrix.length;int n = matrix[0].length;int i = m-1, j=0;while (i>=0 && j<n) {if (matrix[i][j] == target) {return true;}else if (matrix[i][j]<target) {j++;} else {i--;}}return false;}
}

 

  相关解决方案