概述
2019独角兽企业重金招聘Python工程师标准>>>
/**
* 功能:给定M*N矩阵,每一行、每一列都按升序排列,找出某元素。
*/
两种方法:
方法一:
[java] view plain copy
- /**
- * 思路:若列的末端大于x,那么x位于该列的左边;若行的开头小于x,那么x位于列的下边。从矩阵中的子矩阵中查找元素。
- * @param matrix
- * @param elem
- * @return
- */
- public static boolean findElement(int[][] matrix,int elem){
- int row=0;
- int col=matrix[0].length-1;
- while(row<matrix.length&&col>=0){
- if(matrix[row][col]==elem)
- return true;
- else if(matrix[row][col]>elem)
- col--;
- else
- row++;
- }
- return false;
- }
方法二:
[java] view plain copy
- /**
- * 思路:由于每一个元素都大于它左边和上边的元素,所以,若在矩阵里任意画长方形,其右下角的元素一定是最大的,左上角的元素一定是最小的。
- * 将矩阵分为四个区域,以递归方式搜索左下区域和右上区域。
- * @param matrix
- * @param elem
- */
- 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<matrix.length&&column>=0&&column<matrix[0].length;
- }
- 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);
}
}
或者:
方法一:从矩阵的右上角开始找
[cpp] view plain copy
- bool HasElement(vector<vector<int>> martix,int elem)
- {
- if(martix.empty() || martix[0].empty())
- return false;
- int row=0,col=martix[0].size()-1;//右上角元素
- while(row<martix.size() && col>=0)
- {
- if(martix[row][col]==elem)
- return true;
- else if(martix[row][col]>elem)
- col--;
- else
- row++;
- }
- return false;
- }
方法二:从矩阵的左下角开始找
[cpp] view plain copy
- bool HasElement(vector<vector<int>> martix,int elem)
- {
- if(martix.empty() || martix[0].empty())
- return false;
- int row=martix.size()-1,col=0;//左下角元素
- while(row>=0 && col<martix[0].size())
- {
- if(martix[row][col]==elem)
- return true;
- else if(martix[row][col]<elem)
- col++;
- else
- row--;
- }
- return false;
- }
转载于:https://my.oschina.net/u/2822116/blog/793325
最后
以上就是潇洒翅膀为你收集整理的给定M*N矩阵,每一行、每一列都按升序排列,找出某元素的全部内容,希望文章能够帮你解决给定M*N矩阵,每一行、每一列都按升序排列,找出某元素所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复