Search a 2D Matrix(在二维数组中查寻)

Search a 2D Matrix(在二维数组中查找)

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.

For example,

Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

LeetCode上的一道题，这个题比较特殊，如果从二维数组在内存中的存储来看，其实是一个排序的一位数组（自行查阅二维数组在内存的顺序）。所以肯定搞个二分查找就OK了。但是可以先探讨其他方案。

方案1：由于本人审题比较轻率，没有看到本行第一个比上一行最后一个大的条件，看成了本行第一个比上一行第一个大。显然如果这样的话，就会更难处理：

我的方案是先按第一列处理，二分查找找到行，然后行内二分查找。渣代码如下：

public boolean searchMatrix1(int[][] matrix, int target) {
    	int low = 0;
        int high = matrix.length-1;
        int mid = 0;
        while (low <= high) {
        	mid = low + (high-low)/2;
        	if (matrix[mid][0] <= target && target <= matrix[mid][matrix[mid].length-1]) {
        		break;
        	} else if (matrix[mid][matrix[mid].length-1] < target){
        		low = mid +1;
        	} else if (matrix[mid][0] > target){
        		high = mid -1;
        	}
        }
        int row = mid;
        low = 0;
        high = matrix[row].length-1;
        while (low <= high) {
        	mid = low + (high-low)/2;
        	if (matrix[row][mid] == target) {
        		return true;
        	} else if (matrix[row][mid] < target) {
        		low = mid+1;
        	} else {
        		high = mid -1;
        	}
        }
        return false;
    }

其实时间复杂度也就O(lgn+lgm);也算挺快的。

但是由于本题的特殊之处，直接按一维数组处理，渣代码如下：

public boolean searchMatrix(int[][] matrix, int target) {
		int row = matrix.length;
		int col = matrix[0].length;
		int low = 0; 
		int high = row * col -1;
		while (low <= high) {
			int mid = low + (high-low)/2;
			int num = matrix[mid/col][mid%col];
			if (num == target) {
				return true;
			} else if (num < target) {
				low = mid+1;
			} else {
				high = mid-1;
			}
		}
		return false;
    }

时间复杂度O(lg(m+n))；但是由于现在计算机缓存的问题，其实速度没有提升多少。

再看剑指offer的一道题目：

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上往下递增的顺序排序。请写一个函数，输入一个二维数组和一个整数，判断数组中是否含有该整数。

例如下面的二维数组就是每行、每列都是递增顺序，如果在这个数组中查找数字7，则返回true，如果查找数字5，由于数组中不含有该数字，则返回false。

1 2 8 9

2 4 9 12

4 7 10 13

6 8 11 15

public boolean find(int[][] matrix, int number) {
		if (matrix != null && matrix.length > 0 && matrix[0].length > 0) {
			int rows = matrix.length;
			int columns = matrix[0].length;
			int row = 0;
			int col = columns-1;
			while (row < rows && col >= 0) {
				int temp = matrix[row][col];
				if (number > temp) {
					row++;
				} else if (number < temp) {
					col--;
				} else {
					return true;
				}
			}
		}
		return false;
	}

时间复杂度是多少？O(m+n)，岂不是还没有我开始第一种方法效率高？

Search a 2D Matrix(在二维数组中查寻)

相关推荐