[LeetCode] 74. Search a 2D Matrix

轉自LeetCode

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.

<Solution>

從題目知道，first col 和每個 row 是有排序的規則在

那麼就可以利用這一點

想法如下

• 看哪一個 first col 的元素 matrix[row][0] 是小於或等於 target 的，等於當然就回傳 true，小於就代表 target 會落在此 row

• 接著從該 row 的後面往前找，如果有找到就回傳 true，沒有就回傳 false

code 如下，O(mxn)

	class Solution {
	public:
	bool searchMatrix(vector<vector<int>>& matrix, int target) {
	if(matrix.empty() || matrix[0][0] > target || matrix.back().back() < target) {
	return false;
	}
	const int m = matrix.size(), n = matrix[0].size();
	//> find row position
	int row = m-1;
	while(row >= 0 && matrix[row][0] > target) {
	--row;
	}
	if(matrix[row][0] == target) {
	return true;
	}
	//> find col position
	int col = n-1;
	while(col >= 0 && matrix[row][col] != target) {
	--col;
	}
	return (col < 0) ? false : true;
	}
	};

view raw searchIn2DMatrix_1.cpp hosted with ❤ by GitHub

或者，可以針對 row 和 col 做兩次 binary search

這樣可以優化到O(logM + logN)

code 如下
c++

	class Solution {
	public:
	bool searchMatrix(vector<vector<int>>& matrix, int target) {
	if(matrix.empty() || matrix[0][0] > target || matrix.back().back() < target) {
	return false;
	}
	//> use binary search to find row position
	int up = 0, down = matrix.size()-1;
	while(up <= down) {
	int mid = (up + down) / 2;
	if(matrix[mid][0] == target) {
	return true;
	}
	else if(matrix[mid][0] > target) {
	down = mid-1;
	}
	else {
	up = mid+1;
	}
	}
	int row = down; //> possibile row
	//> use binary search to find target in specific row
	int left = 0, right = matrix[row].size();
	while(left <= right) {
	int mid = (left + right) / 2;
	if(matrix[row][mid] == target) {
	return true;
	}
	else if(matrix[row][mid] < target) {
	left = mid + 1;
	}
	else {
	right = mid - 1;
	}
	}
	return false;
	}
	};

view raw searchIn2DMatrix_2.cpp hosted with ❤ by GitHub

Kotlin

	class Solution {
	fun searchMatrix(matrix: Array<IntArray>, target: Int): Boolean {
	var up = 0
	var down = matrix.size
	while(up < down) {
	val mid = up + (down - up) / 2
	when {
	matrix[mid][0] == target -> return true
	matrix[mid][0] < target -> up = mid+1
	else -> down = mid
	}
	}
	--down
	if(down < 0) {
	return false
	}
	var left = 0
	var right = matrix[0].size
	while(left < right) {
	val mid = left + (right - left) / 2
	when {
	matrix[down][mid] == target -> return true
	matrix[down][mid] < target -> left = mid+1
	else -> right = mid
	}
	}
	return false
	}
	}

view raw search_a_2D_matrix.kt hosted with ❤ by GitHub