文档章节

给定M*N矩阵,每一行、每一列都按升序排列,找出某元素

一贱书生
 一贱书生
发布于 2016/11/24 08:47
字数 871
阅读 369
收藏 0

#程序员薪资揭榜#你做程序员几年了?月薪多少?发量还在么?>>>

/**

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

 */

 

两种方法:

 

方法一:

[java] view plain copy

 

  1. /** 
  2.  * 思路:若列的末端大于x,那么x位于该列的左边;若行的开头小于x,那么x位于列的下边。从矩阵中的子矩阵中查找元素。 
  3.  * @param matrix 
  4.  * @param elem 
  5.  * @return 
  6.  */  
  7. public static boolean findElement(int[][] matrix,int elem){  
  8.     int row=0;  
  9.     int col=matrix[0].length-1;  
  10.       
  11.     while(row<matrix.length&&col>=0){  
  12.         if(matrix[row][col]==elem)  
  13.             return true;  
  14.         else if(matrix[row][col]>elem)  
  15.             col--;  
  16.         else  
  17.             row++;  
  18.     }  
  19.     return false;  
  20. }  

 

方法二:

 

[java] view plain copy

 

  1. /** 
  2.  * 思路:由于每一个元素都大于它左边和上边的元素,所以,若在矩阵里任意画长方形,其右下角的元素一定是最大的,左上角的元素一定是最小的。 
  3.  * 将矩阵分为四个区域,以递归方式搜索左下区域和右上区域。 
  4.  * @param matrix 
  5.  * @param elem 
  6.  */  
  7. public void findElement2(int[][] matrix,int elem){  
  8.     Coordinate origin=new Coordinate(0,0);  
  9.     Coordinate dest=new Coordinate(matrix.length-1,matrix[0].length-1);  
  10.     find(matrix, origin, dest, elem);  
  11. }  
  12.   
  13. public Coordinate find(int[][] matrix,Coordinate origin,Coordinate dest,int x){  
  14.     if(!origin.inBounds(matrix)||!dest.inBounds(matrix))  
  15.         return null;  
  16.       
  17.     if(matrix[origin.row][origin.column]==x)  
  18.         return origin;  
  19.     else if(!origin.isBefore(dest))  
  20.         return null;  
  21.       
  22.     //start和end 分别设为对角线的起点和终点,矩阵不一定是正方形,因此对角线的终点也不一定是dest。  
  23.     Coordinate start=(Coordinate) origin.clone();  
  24.     int distance=Math.min(dest.row-origin.row, dest.column-origin.column);  
  25.       
  26.     Coordinate end=new Coordinate(start.row+distance, start.column+distance);  
  27.       
  28.     Coordinate p=new Coordinate(0,0);  
  29.       
  30.     //在对角线上进行二分查找  
  31.     while(start.isBefore(end)){  
  32.         p.setToAverage(start, end);  
  33.         if(x>matrix[p.row][p.column]){  
  34.             start.row=p.row+1;  
  35.             start.column=p.column+1;  
  36.         }else{  
  37.             end.row=p.row-1;  
  38.             end.column=p.column-1;  
  39.         }  
  40.     }  
  41.     //将矩阵分为四个区域,搜索左下区域和右上区域  
  42.     return partitionAandSearch(matrix,origin,dest,start,x);  
  43.       
  44. }  
  45.   
  46. public Coordinate partitionAandSearch(int[][] matrix,Coordinate origin,Coordinate dest,Coordinate pivot,int elem){  
  47.     Coordinate lowerLeftOrigin=new Coordinate(pivot.row, origin.column);  
  48.     Coordinate lowerLeftDest=new Coordinate(dest.row,pivot.column-1);  
  49.       
  50.     Coordinate upperRightOrigin=new Coordinate(origin.row,pivot.column);  
  51.     Coordinate upperRightDest=new Coordinate(pivot.row-1,dest.column);  
  52.       
  53.     Coordinate lowerLeft=find(matrix, lowerLeftOrigin, lowerLeftDest, elem);  
  54.     if(lowerLeft==null)  
  55.         return find(matrix, upperRightOrigin, upperRightDest, elem);  
  56.     return lowerLeft;  
  57. }  
  58.   
  59.   
  60.   
  61. lass Coordinate implements Cloneable{  
  62. public int row;  
  63. public int column;  
  64. public Coordinate(int r,int c){  
  65.     this.row=c;  
  66.     this.column=c;  
  67. }  
  68.   
  69. public boolean inBounds(int[][] matrix){  
  70.     return row>=0&&row<matrix.length&&column>=0&&column<matrix[0].length;  
  71. }  
  72.   
  73. public boolean isBefore(Coordinate p){  
  74.     return this.row<=p.row&&this.column<=p.column;  
  75. }  
  76.   
  77. public Object clone(){  
  78.     return new Coordinate(row,column);  
  79. }  
  80.   
  81. public void setToAverage(Coordinate min,Coordinate max){  
  82.     row=(min.row+max.row)/2;  
  83.     column=(min.column+max.column)/2;  
  84. }

或者

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

 

  1. bool HasElement(vector<vector<int>> martix,int elem)  
  2. {  
  3.     if(martix.empty() || martix[0].empty())  
  4.         return false;  
  5.     int row=0,col=martix[0].size()-1;//右上角元素  
  6.     while(row<martix.size() && col>=0)  
  7.     {  
  8.         if(martix[row][col]==elem)  
  9.             return true;  
  10.         else if(martix[row][col]>elem)  
  11.             col--;  
  12.         else  
  13.             row++;  
  14.     }  
  15.     return false;  
  16. }  


 

 

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

 

[cpp] view plain copy

 

  1. bool HasElement(vector<vector<int>> martix,int elem)  
  2. {  
  3.     if(martix.empty() || martix[0].empty())  
  4.         return false;  
  5.     int row=martix.size()-1,col=0;//左下角元素  
  6.     while(row>=0 && col<martix[0].size())  
  7.     {  
  8.         if(martix[row][col]==elem)  
  9.             return true;  
  10.         else if(martix[row][col]<elem)  
  11.             col++;  
  12.         else  
  13.             row--;  
  14.     }  
  15.     return false;  
  16. }

© 著作权归作者所有

一贱书生
粉丝 21
博文 723
码字总数 600123
作品 0
私信 提问
加载中

评论(0)

leetcode240——搜索二维矩阵(medium)

一、题目描述 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性: 每行的元素从左到右升序排列。 每列的元素从上到下升序排列。 示例: 现有矩阵 matr...

404found
05/09
0
0
leetcode.矩阵.240搜索二维矩阵II-Java

具体题目 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性:每行的元素从左到右升序排列;每列的元素从上到下升序排列。 示例:  现有矩阵 matrix...

osc_bc7dotjc
2019/11/21
2
0
《Java练习题》Java进阶练习题(四)

编程合集: https://www.cnblogs.com/jssj/p/12002760.html 前言:不仅仅要实现,更要提升性能,精益求精,用尽量少的时间复杂度和空间复杂度解决问题。 【程序78】 实现获取下一个排列的函数...

osc_h9x23mw1
2019/12/07
3
0
LeetCode 240 - 搜索二维矩阵 II

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性: 每行的元素从左到右升序排列。 每列的元素从上到下升序排列。 示例: 现有矩阵 matrix 如下: [ ...

osc_ejr00qw0
2019/04/26
1
0
leetcode 刷题 算法 1

只出现一次的数字 给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。 class Solution {public: }; 说明:采用异或,0与任何数异或得...

osc_nrqfdybm
2019/03/09
3
0

没有更多内容

加载失败,请刷新页面

加载更多

ThreadLocal

一、ThreadLocal简介   多线程访问同一个共享变量的时候容易出现并发问题,特别是多个线程对一个变量进行写入的时候,为了保证线程安全,一般使用者在访问共享变量的时候需要进行额外的同步...

architect刘源源
昨天
15
0
微信小程序客服会话卡片、自定义客服消息卡片

一、微信客服会话启用会话卡片 1. open-type="contact" 2. show-message-card =true 更多参考官方文档: https://developers.weixin.qq.com/miniprogram/dev/component/button.html 当前效果......

tianma3798
昨天
6
0
练习Linux常用命令

练习命令 Linux常用命令 Linux中一切皆文件,没有消息就是最好的消息 以下所有命令以centos7为基础, 网络相关配置 测试外网是否连通 安装网卡测试工具,即ifconfig程序 查看网卡 临时修改I...

千年典韦
昨天
10
0
从poison社网站爬取历代作品资料

使用的语言是python,爬取使用的代码包在我的主页有提供. 其中一些相关的数据设定如下(复制为data.py,然后运行主页提供的包的main.py): from mypython import *CODE = '4fjl_fjiepq24x' #...

setycyas
昨天
36
0
确定已安装的PowerShell版本 - Determine installed PowerShell version

问题: 如何确定计算机上安装了哪个版本的PowerShell,以及是否确实安装了该版本? 解决方案: 参考一: https://stackoom.com/question/7euv/确定已安装的PowerShell版本 参考二: https://...

技术盛宴
昨天
24
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部