Leetcode[74, 240] Search a 2D Matrix
29 Nov 2015###Task1 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
###Python
class Solution(object):
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
m = len(matrix)
n = len(matrix[0])
l = 0
r = m * n - 1
while l + 1 < r:
mid = l + (r - l) / 2
row = mid / n
col = mid % n
if matrix[row][col] == target:
return True
elif matrix[row][col] > target:
r = mid
else:
l = mid
if matrix[l / n][l % n] == target:
return True
elif matrix[r / n][r % n] == target:
return True
else:
return False
###Java
public class Solution {
public int[] productExceptSelf(int[] nums) {
if (nums == null || nums.length == 0) {
return null;
}
int[] res = new int[nums.length];
int[] left = new int[nums.length];
int[] right = new int[nums.length];
left[0] = 1;
for (int i = 1; i < nums.length; i++) {
left[i] = left[i - 1] * nums[i - 1];
}
right[nums.length - 1] = 1;
for (int i = nums.length - 2; i >= 0; i--) {
right[i] = right[i + 1] * nums[i + 1];
}
for (int i = 0; i < nums.length; i++) {
res[i] = left[i] * right[i];
}
return res;
}
}
###Task2 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 in ascending from left to right. Integers in each column are sorted in ascending from top to bottom. For example,
Consider the following matrix:
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
] Given target = 5, return true.
Given target = 20, return false.
###Python ####O(m + n)
class Solution(object):
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
M = len(matrix)
N = len(matrix[0])
row = M - 1
col = 0
while row >= 0 and col <= N - 1:
if matrix[row][col] == target:
return True
elif matrix[row][col] > target:
row -= 1
else:
col += 1
return False
####O(mlogn), bst
class Solution:
# @param {integer[][]} matrix
# @param {integer} target
# @return {boolean}
def searchMatrix(self, matrix, target):
y = len(matrix[0]) - 1
def binSearch(nums, low, high):
while low <= high:
mid = (low + high) / 2
if nums[mid] > target:
high = mid - 1
else:
low = mid + 1
return high
for x in range(len(matrix)):
y = binSearch(matrix[x], 0, y)
if matrix[x][y] == target:
return True
return False
###Java
public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return false;
}
int row = matrix.length;
int col = matrix[0].length;
int curR = row - 1;
int curC = 0;
while (curR >= 0 && curC <= col - 1) {
if (matrix[curR][curC] == target) {
return true;
} else if (matrix[curR][curC] < target) {
curC++;
} else {
curR--;
}
}
return false;
}
}