java矩阵每行每列最大值_给定M*N矩阵，每一行、每一列都按升序排列，找出某元素...

阳光穿透心脏的1/2处 2022-11-08 14:19 195阅读 0赞

/\*\*

\* 功能：给定M\*N矩阵，每一行、每一列都按升序排列，找出某元素。

\*/

两种方法：

方法一：

/\*\*

\* 思路：若列的末端大于x，那么x位于该列的左边；若行的开头小于x，那么x位于列的下边。从矩阵中的子矩阵中查找元素。

\* @param matrix

\*/

public static boolean findElement(int\[\]\[\] matrix,int elem)\{

int row=0;

int col=matrix\[0\].length-1;

while(row=0)\{

if(matrix\[row\]\[col\]==elem)

return true;

else if(matrix\[row\]\[col\]>elem)

col--;

else

row++;

return false;

方法二：

/\*\*

\* 思路：由于每一个元素都大于它左边和上边的元素，所以，若在矩阵里任意画长方形，其右下角的元素一定是最大的，左上角的元素一定是最小的。

\* 将矩阵分为四个区域，以递归方式搜索左下区域和右上区域。

\* @param matrix

\*/

public void findElement2(int\[\]\[\] matrix,int elem)\{

Coordinate origin=new Coordinate(0,0);

Coordinate dest=new Coordinate(matrix.length-1,matrix\[0\].length-1);

find(matrix, origin, dest, elem);

public Coordinate find(int\[\]\[\] matrix,Coordinate origin,Coordinate dest,int x)\{

if(!origin.inBounds(matrix)||!dest.inBounds(matrix))

return null;

if(matrix\[origin.row\]\[origin.column\]==x)

return origin;

else if(!origin.isBefore(dest))

return null;

//start和end 分别设为对角线的起点和终点，矩阵不一定是正方形，因此对角线的终点也不一定是dest。

Coordinate start=(Coordinate) origin.clone();

int distance=Math.min(dest.row-origin.row, dest.column-origin.column);

Coordinate end=new Coordinate(start.row+distance, start.column+distance);

Coordinate p=new Coordinate(0,0);

//在对角线上进行二分查找

while(start.isBefore(end))\{

p.setToAverage(start, end);

if(x>matrix\[p.row\]\[p.column\])\{

start.row=p.row+1;

start.column=p.column+1;

\}else\{

end.row=p.row-1;

end.column=p.column-1;

//将矩阵分为四个区域，搜索左下区域和右上区域

return partitionAandSearch(matrix,origin,dest,start,x);

public Coordinate partitionAandSearch(int\[\]\[\] matrix,Coordinate origin,Coordinate dest,Coordinate pivot,int elem)\{

Coordinate lowerLeftOrigin=new Coordinate(pivot.row, origin.column);

Coordinate lowerLeftDest=new Coordinate(dest.row,pivot.column-1);

Coordinate upperRightOrigin=new Coordinate(origin.row,pivot.column);

Coordinate upperRightDest=new Coordinate(pivot.row-1,dest.column);

Coordinate lowerLeft=find(matrix, lowerLeftOrigin, lowerLeftDest, elem);

if(lowerLeft==null)

return find(matrix, upperRightOrigin, upperRightDest, elem);

return lowerLeft;

lass Coordinate implements Cloneable\{

public int row;

public int column;

public Coordinate(int r,int c)\{

this.row=c;

this.column=c;

public boolean inBounds(int\[\]\[\] matrix)\{

return row>=0&&row=0&&column

public boolean isBefore(Coordinate p)\{

return this.row<=p.row&&this.column<=p.column;

public Object clone()\{

return new Coordinate(row,column);

public void setToAverage(Coordinate min,Coordinate max)\{

row=(min.row+max.row)/2;

column=(min.column+max.column)/2;

或者

package com.huanchuang.arvin.vo;

public class Finder \{

private String findElement(int\[\]\[\] matrix, int target) \{

int row = 0, column = 0;

// 只要行还没有达到最大值就继续执行

while (row < matrix.length) \{

int colMax = matrix\[row\].length - 1;// 用于获取矩阵每一行的最大值

// 因为是行和列都是赠序的，只要指定的数在每一行的最小值和最大值之间，就返回true

if (matrix\[row\]\[column\] <= target && matrix\[row\]\[colMax\] >= target) \{

for (int i = 0; i < matrix\[row\].length; i++) \{

if (matrix\[row\]\[i\] == target) \{

return "matrix\[" + row + "\]\[" + i + "\]";

\} else \{// 否则的话就自动去下一行进行比较

row++;

return "matrix\[-1\]\[-1\]";// 返回-1表示不存在

public static void main(String\[\] args) \{

int matrix\[\]\[\] = \{ \{ 1, 2, 3 \}, \{ 4, 5 \}, \{ 7, 8, 9 \} \};

Finder finder = new Finder();

String location = finder.findElement(matrix, 6);

System.out.println("位置" + location);

或者：

方法一：从矩阵的右上角开始找

bool HasElement(vector> martix,int elem)

if(martix.empty() || martix\[0\].empty())

return false;

int row=0,col=martix\[0\].size()-1;//右上角元素

while(row=0)

if(martix\[row\]\[col\]==elem)

return true;

else if(martix\[row\]\[col\]>elem)

col--;

else

row++;

return false;

方法二：从矩阵的左下角开始找

bool HasElement(vector> martix,int elem)

if(martix.empty() || martix\[0\].empty())

return false;

int row=martix.size()-1,col=0;//左下角元素

while(row>=0 && col

if(martix\[row\]\[col\]==elem)

return true;

else if(martix\[row\]\[col\]

col++;

else

row--;

return false;

java矩阵每行每列最大值_给定M*N矩阵，每一行、每一列都按升序排列，找出某元素...

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关 MATLAB矩阵A和矩阵B的每一列分别点乘

相关 python 读取txt按逗哈每一列

相关动态定义table每行两列

相关 java矩阵每行每列最大值_给定M*N矩阵，每一行、每一列都按升序排列，找出某元素...

相关 c语言2维数组每一行最小值,二维数组每一行最大值

相关 C语言——求二维数组每列元素最大值。

相关在杨氏矩阵中找数字，存在返回下标，不存在返回“不存在”，杨氏矩阵：每行每列的数字都是递增排序的

相关 Valid Sudoku(每行、每列、3x3都为1到9)leetcode36

相关 C语言输出每一行的最大数字和每一列的最小数字（使用动态数组实现）

相关 mysql 按每小时分组统计（行转列）