文档章节

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

一贱书生
 一贱书生
发布于 2016/11/24 08:47
字数 871
阅读 4
收藏 0
点赞 0
评论 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. }

© 著作权归作者所有

共有 人打赏支持
一贱书生
粉丝 19
博文 722
码字总数 600072
作品 0
强大的矩阵奇异值分解(SVD)及其应用

一、奇异值与特征值基础知识: 特征值分解和奇异值分解在机器学习领域都是属于满地可见的方法。两者有着很紧密的关系,我在接下来会谈到,特征值分解和奇异值分解的目的都是一样,就是提取出...

liangtee ⋅ 2013/03/30 ⋅ 0

PCA (主成分分析)详解 (写给初学者) 结合matlab

(转载请注明出处) 一、简介 PCA(Principal Components Analysis)即主成分分析,是图像处理中经常用到的降维方法,大家知道,我们在处理有关数字图像处理方面的问题时,比如经常用的图像的...

代码学习者01 ⋅ 2014/04/22 ⋅ 2

矩阵奇异值分解(SVD)及其应用

一、奇异值与特征值基础知识 特征值分解和奇异值分解在机器学习领域都是属于满地可见的方法。两者有着很紧密的关系,我在接下来会谈到,特征值分解和奇异值分解的目的都是一样,就是提取出一...

SVD ⋅ 2015/12/23 ⋅ 1

基于MATLAB的贝叶斯网络工具箱BNT的安装和使用_2

一、图的邻接矩阵(Adjacency Matrix)表示 拓扑网络图中的两个节点相邻或邻接,是指节点之间至少有一条边。把图转换为邻接矩阵的表示方式,主要是确定相邻节点边的数目。有如下参考图 图中共...

阳_ ⋅ 2013/09/21 ⋅ 0

学习笔记DL004:标量、向量、矩阵、张量,矩阵、向量相乘,单位矩阵、逆矩阵

线性代数,面向连续数学,非离散数学。《The Matrix Cookbook》,Petersen and Pedersen,2006。Shilov(1977)。 标量、向量、矩阵、张量。 标量(scalar)。一个标量,一个单独的数。其他大部分...

利炳根 ⋅ 2017/11/20 ⋅ 0

给定一个由整数组成二维矩阵(r*c),现在需要找出它的一个子矩阵,使得这个子矩阵内的所有元素之和最大,并把这个子矩阵称为最大子矩阵。

题目描述 有一个正整数和负整数组成的NxN矩阵,请编写代码找出元素总和最大的子矩阵。请尝试使用一个高效算法。 给定一个int矩阵mat和矩阵的阶数n,请返回元素总和最大的子矩阵的元素之和。保...

一贱书生 ⋅ 2016/11/29 ⋅ 0

linux关于处理文本内容的命令!!

最近学习了 一些处理文本内容的命令今天总结一下,以便以后复习! 以下命令只列出了一些常用参数. uniq 命令 uniq 命令不加参数可以去除出文件中重复行(这些重复的行必须相邻,不相邻不能去除)...

求学ing ⋅ 2013/03/22 ⋅ 0

深度学习算法:SVD分解算法及其应用

From: http://www.tuicool.com/articles/bEfMZr 矩阵的奇异值分解在矩阵理论的重要性不言而喻,它在最优化问题、特征值问题、最小乘方问题、广义逆矩阵问,统计学,图像压缩等方面都有十分重要...

xuzheng_1982 ⋅ 2017/01/18 ⋅ 0

LeetCode:Set Matrix Zeroes - 将矩阵内含有零的行和列全部置零

1、题目名称 Set Matrix Zeroes(将矩阵内含有零的行和列全部置零) 2、题目地址 https://leetcode.com/problems/set-matrix-zeroes/ 3、题目内容 英文:Given a m x n matrix, if an eleme...

北风其凉 ⋅ 2015/11/07 ⋅ 0

C#计算矩阵的秩

1.代码思路 计算矩阵的秩,即把矩阵进行行初等变换,得出的行最简矩阵的非零行数。过程如下 1)将矩阵各行按第一个非零元素出现的位置升序排列(Operation1函数) 2)查看矩阵是否为行最简矩...

北风其凉 ⋅ 2014/04/23 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

十五周二次课

十五周二次课 17.1mysql主从介绍 17.2准备工作 17.3配置主 17.4配置从 17.5测试主从同步 17.1mysql主从介绍 MySQL主从介绍 MySQL主从又叫做Replication、AB复制。简单讲就是A和B两台机器做主...

河图再现 ⋅ 52分钟前 ⋅ 0

docker安装snmp rrdtool环境

以Ubuntu16:04作为基础版本 docker pull ubuntu:16.04 启动一个容器 docker run -d -i -t --name flow_mete ubuntu:16.04 bash 进入容器 docker exec -it flow_mete bash cd ~ 安装基本软件 ......

messud4312 ⋅ 今天 ⋅ 0

OSChina 周一乱弹 —— 快别开心了,你还没有女友呢。

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @莱布妮子 :分享吴彤的单曲《好春光》 《好春光》- 吴彤 手机党少年们想听歌,请使劲儿戳(这里) @clouddyy :小萝莉街上乱跑,误把我认错成...

小小编辑 ⋅ 今天 ⋅ 7

mysql in action / alter table

change character set ALTER SCHEMA `employees` DEFAULT CHARACTER SET utf8mb4 DEFAULT COLLATE utf8mb4_general_ci ;ALTER TABLE `employees`.`t2` CHARACTER SET = utf8mb4 , COLLAT......

qwfys ⋅ 今天 ⋅ 0

Java 开发者不容错过的 12 种高效工具

Java 开发者常常都会想办法如何更快地编写 Java 代码,让编程变得更加轻松。目前,市面上涌现出越来越多的高效编程工具。所以,以下总结了一系列工具列表,其中包含了大多数开发人员已经使用...

jason_kiss ⋅ 昨天 ⋅ 0

Linux下php访问远程ms sqlserver

1、安装freetds(略,安装在/opt/local/freetds 下) 2、cd /path/to/php-5.6.36/ 进入PHP源码目录 3、cd ext/mssql进入MSSQL模块源码目录 4、/opt/php/bin/phpize生成编译配置文件 5、 . ./...

wangxuwei ⋅ 昨天 ⋅ 0

如何成为技术专家

文章来源于 -- 时间的朋友 拥有良好的心态。首先要有空杯心态,用欣赏的眼光发现并学习别人的长处,包括但不限于工具的使用,工作方法,解决问题以及规划未来的能力等。向别人学习的同时要注...

长安一梦 ⋅ 昨天 ⋅ 0

Linux vmstat命令实战详解

vmstat命令是最常见的Linux/Unix监控工具,可以展现给定时间间隔的服务器的状态值,包括服务器的CPU使用率,内存使用,虚拟内存交换情况,IO读写情况。这个命令是我查看Linux/Unix最喜爱的命令...

刘祖鹏 ⋅ 昨天 ⋅ 0

MySQL

查看表相关命令 - 查看表结构    desc 表名- 查看生成表的SQL    show create table 表名- 查看索引    show index from  表名 使用索引和不使用索引 由于索引是专门用于加...

stars永恒 ⋅ 昨天 ⋅ 0

easyui学习笔记

EasyUI常用控件禁用方法 combobox $("#id").combobox({ disabled: true }); ----- $("#id").combobox({ disabled: false}); validatebox $("#id").attr("readonly", true); ----- $("#id").r......

miaojiangmin ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部