LeetCode 74:Search a 2D Matrix

Datetime:2016-08-23 01:21:46          Topic: LeetCode           Share

Write an efficient algorithm that searches for a value in an mn 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 target3 , return  true .

Subscribe to see which companies asked this question

class Solution {
 public:
	 bool searchMatrix(vector<vector<int>>& matrix, int target) {
		 if (matrix.size() == 0)     return false;
		 if (matrix[0][0] > target)  return false;
		 int r = matrix.size(), c = matrix[0].size(); //r,c分别为矩阵matrix的行数和列数
		 int low = 0, high = r-1;

		 //在所有行中利用二分查找target所在的行
		while(low <= high)
		 {
			 int mid = low + (high-low) / 2;
			 if (matrix[mid][0] == target)
				 return true;
			 else if (matrix[mid][0] < target)
				 low = mid + 1;
			 else
				 high = mid - 1;
		 }

		//在target所在行中利用二分查找target
		int low1 = 0, high1 = c - 1;
		int k = 0;
		while (low1 <= high1)
		{
			int mid1 = low1 + (high1 - low1)/2;
			if (matrix[low-1][mid1] == target) //注意target所在的行是(low-1)
				return true;
			else if (matrix[low-1][mid1] < target)
				low1 = mid1 + 1;
			else
				high1 = mid1 - 1;

			k = mid1;
		}
		
		if (matrix[low-1][k] == target) 
			return true;
		else
			return false;
	 }
 };

测试代码:

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

 class Solution {
 public:
	 bool searchMatrix(vector<vector<int>>& matrix, int target) {
		 if (matrix.size() == 0)     return false;
		 if (matrix[0][0] > target)  return false;
		 int r = matrix.size(), c = matrix[0].size(); //r,c分别为矩阵matrix的行数和列数
		 int low = 0, high = r-1;

		 //在所有行中利用二分查找target所在的行
		while(low <= high)
		 {
			 int mid = low + (high-low) / 2;
			 if (matrix[mid][0] == target)
				 return true;
			 else if (matrix[mid][0] < target)
				 low = mid + 1;
			 else
				 high = mid - 1;
		 }

		//在target所在行中利用二分查找target
		int low1 = 0, high1 = c - 1;
		int k = 0;
		while (low1 <= high1)
		{
			int mid1 = low1 + (high1 - low1)/2;
			if (matrix[low-1][mid1] == target) //注意target所在的行是(low-1)
				return true;
			else if (matrix[low-1][mid1] < target)
				low1 = mid1 + 1;
			else
				high1 = mid1 - 1;

			k = mid1;
		}
		
		if (matrix[low-1][k] == target) 
			return true;
		else
			return false;
	 }
 };


int main()
{
	Solution s;
	vector<vector<int>> nums1 = { { 1, 3, 5, 7 }, { 10, 11, 16, 20 }, {23,30,34,50} };
	bool  t = s.searchMatrix(nums1, 11);
	cout << t <<endl;
	system("pause");
	return 0;
}




About List