Repository navigation
Expand file tree
/
Copy pathsearch2DMatrix.II.cpp
More file actions
151 lines (125 loc) · 4.56 KB
/
Copy pathsearch2DMatrix.II.cpp
File metadata and controls
151 lines (125 loc) · 4.56 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
// Source : https://leetcode.com/problems/search-a-2d-matrix-ii/
// Author : Hao Chen
// Date : 2015-08-15
/**********************************************************************************
*
* 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.
*
*
*
*
**********************************************************************************/
class Solution {
public:
bool binary_search(vector<int> &v, int target) {
int low = 0;
int high = v.size()-1;
while(low <= high) {
int mid = low + (high - low)/2;
if (target == v[mid]) return true;
if (target < v[mid]) {
high = mid -1;
}else {
low = mid + 1;
}
}
return false;
}
//using binary_search() to search each rows - slow O(n*log(n))
//the run time is around 840ms for all test case
bool searchMatrix01(vector<vector<int>>& matrix, int target) {
for (int i=0; i<matrix.size(); i++){
if (target < matrix[i][0] ) return false;
if (binary_search(matrix[i], target)) return true;
}
return false;
}
//start the liner search from top right corner of matrix. - O(m+n)
//the run time is around 340ms
bool searchMatrix02(vector<vector<int>>& matrix, int target) {
if (matrix.size() == 0 || matrix[0].size()==0) return false;
int row=0, col = matrix[0].size() - 1;
while (row < matrix.size() && col >=0 ) {
if (target == matrix[row][col]) return true;
if (target < matrix[row][col]) {
col--;
}else{
row++;
}
}
return false;
}
//a bit optimization for methed 2 - the run time is 300ms
bool searchMatrix021(vector<vector<int>>& matrix, int target) {
if (matrix.size() == 0 || matrix[0].size()==0) return false;
int row=0, col = matrix[0].size() - 1;
while (row < matrix.size() && col >=0 ) {
if (target == matrix[row][col]) return true;
while ( col>=0 && target < matrix[row][col]) {
col--;
}
while(row < matrix.size() && target > matrix[row][col]){
row++;
}
}
return false;
}
//Optimization: using binary search methed to move `low` and `row`
//however, the run time is around 830ms
bool searchMatrix022(vector<vector<int>>& matrix, int target) {
if (matrix.size() == 0 || matrix[0].size()==0) return false;
int row=0, col = matrix[0].size() - 1;
while (row < matrix.size() && col >=0 ) {
if (target == matrix[row][col]) return true;
if (target < matrix[row][col]) {
int start=0, end=col;
while(start <= end){
int mid = start + (end - start)/2;
if (target == matrix[row][mid]) return true;
if (target > matrix[row][mid]) {
col = start = mid + 1;
}else {
col = end = mid - 1;
}
}
}else{
int start=0, end=row;
while(start<=end){
int mid = start + (end - start)/2;
if (target == matrix[mid][col]) return true;
if (target > matrix[mid][col]) {
row = start = mid + 1;
}else{
row = end = mid -1;
}
}
}
}
return false;
}
bool searchMatrix(vector<vector<int>>& matrix, int target) {
return searchMatrix022(matrix, target); //840ms ??
return searchMatrix021(matrix, target); //320ms
return searchMatrix02(matrix, target); //340ms
return searchMatrix01(matrix, target); // 840ms
}
};