Skip to content

Commit f3f99f0

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lc problem: No.0074. Search a 2D Matrix
1 parent 1c87e8e commit f3f99f0

File tree

7 files changed

+170
-121
lines changed

7 files changed

+170
-121
lines changed

‎solution/0000-0099/0074.Search a 2D Matrix/README.md

Lines changed: 59 additions & 41 deletions
Original file line numberDiff line numberDiff line change
@@ -56,17 +56,15 @@
5656
class Solution:
5757
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
5858
m, n = len(matrix), len(matrix[0])
59-
l, h = 0, m * n - 1
60-
while l <= h:
61-
mid = (l + h) >> 1
59+
left, right = 0, m * n - 1
60+
while left < right:
61+
mid = (left + right) >> 1
6262
x, y = divmod(mid, n)
63-
if matrix[x][y] == target:
64-
return True
65-
if matrix[x][y] < target:
66-
l = mid + 1
63+
if matrix[x][y] >= target:
64+
right = mid
6765
else:
68-
h = mid - 1
69-
return False
66+
left = mid + 1
67+
return matrix[left // n][left % n] == target
7068
```
7169

7270
### **Java**
@@ -77,15 +75,17 @@ class Solution:
7775
class Solution {
7876
public boolean searchMatrix(int[][] matrix, int target) {
7977
int m = matrix.length, n = matrix[0].length;
80-
int l = 0, h = m * n - 1;
81-
while (l <= h) {
82-
int mid = (l + h) >>> 1;
78+
int left = 0, right = m * n - 1;
79+
while (left < right) {
80+
int mid = (left + right) >> 1;
8381
int x = mid / n, y = mid % n;
84-
if (matrix[x][y] == target) return true;
85-
if (matrix[x][y] < target) l = mid + 1;
86-
else h = mid - 1;
82+
if (matrix[x][y] >= target) {
83+
right = mid;
84+
} else {
85+
left = mid + 1;
86+
}
8787
}
88-
return false;
88+
return matrix[left / n][left % n] == target;
8989
}
9090
}
9191
```
@@ -97,15 +97,17 @@ class Solution {
9797
public:
9898
bool searchMatrix(vector<vector<int>>& matrix, int target) {
9999
int m = matrix.size(), n = matrix[0].size();
100-
int l = 0, h = m * n - 1;
101-
while (l <= h) {
102-
int mid = l + ((h - l) >> 1);
100+
int left = 0, right = m * n - 1;
101+
while (left < right) {
102+
int mid = left + right >> 1;
103103
int x = mid / n, y = mid % n;
104-
if (matrix[x][y] == target) return true;
105-
if (matrix[x][y] < target) l = mid + 1;
106-
else h = mid - 1;
104+
if (matrix[x][y] >= target) {
105+
right = mid;
106+
} else {
107+
left = mid + 1;
108+
}
107109
}
108-
return false;
110+
return matrix[left / n][left % n] == target;
109111
}
110112
};
111113
```
@@ -118,28 +120,44 @@ public:
118120
* @param {number} target
119121
* @return {boolean}
120122
*/
121-
var searchMatrix = function (matrix, target) {
122-
const m = matrix.length;
123-
const n = matrix[0].length;
124-
let l = 0;
125-
let h = m * n - 1;
126-
while (l <= h) {
127-
const mid = (l + h) >>> 1;
128-
const x = Math.floor(mid / n);
129-
const y = mid % n;
130-
if (matrix[x][y] == target) {
131-
return true;
132-
}
133-
if (matrix[x][y] < target) {
134-
l = mid + 1;
135-
} else {
136-
h = mid - 1;
123+
var searchMatrix = function(matrix, target) {
124+
const m = matrix.length;
125+
const n = matrix[0].length;
126+
let left = 0;
127+
let right = m * n - 1;
128+
while (left < right) {
129+
const mid = (left + right) >> 1;
130+
const x = Math.floor(mid / n);
131+
const y = mid % n;
132+
if (matrix[x][y] >= target) {
133+
right = mid;
134+
} else {
135+
left = mid + 1;
136+
}
137137
}
138-
}
139-
return false;
138+
return matrix[Math.floor(left / n)][left % n] == target;
140139
};
141140
```
142141

142+
### **Go**
143+
144+
```go
145+
func searchMatrix(matrix [][]int, target int) bool {
146+
m, n := len(matrix), len(matrix[0])
147+
left, right := 0, m*n-1
148+
for left < right {
149+
mid := (left + right) >> 1
150+
x, y := mid/n, mid%n
151+
if matrix[x][y] >= target {
152+
right = mid
153+
} else {
154+
left = mid + 1
155+
}
156+
}
157+
return matrix[left/n][left%n] == target
158+
}
159+
```
160+
143161
### **...**
144162

145163
```

‎solution/0000-0099/0074.Search a 2D Matrix/README_EN.md

Lines changed: 59 additions & 41 deletions
Original file line numberDiff line numberDiff line change
@@ -46,17 +46,15 @@
4646
class Solution:
4747
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
4848
m, n = len(matrix), len(matrix[0])
49-
l, h = 0, m * n - 1
50-
while l <= h:
51-
mid = (l + h) >> 1
49+
left, right = 0, m * n - 1
50+
while left < right:
51+
mid = (left + right) >> 1
5252
x, y = divmod(mid, n)
53-
if matrix[x][y] == target:
54-
return True
55-
if matrix[x][y] < target:
56-
l = mid + 1
53+
if matrix[x][y] >= target:
54+
right = mid
5755
else:
58-
h = mid - 1
59-
return False
56+
left = mid + 1
57+
return matrix[left // n][left % n] == target
6058
```
6159

6260
### **Java**
@@ -65,15 +63,17 @@ class Solution:
6563
class Solution {
6664
public boolean searchMatrix(int[][] matrix, int target) {
6765
int m = matrix.length, n = matrix[0].length;
68-
int l = 0, h = m * n - 1;
69-
while (l <= h) {
70-
int mid = (l + h) >>> 1;
66+
int left = 0, right = m * n - 1;
67+
while (left < right) {
68+
int mid = (left + right) >> 1;
7169
int x = mid / n, y = mid % n;
72-
if (matrix[x][y] == target) return true;
73-
if (matrix[x][y] < target) l = mid + 1;
74-
else h = mid - 1;
70+
if (matrix[x][y] >= target) {
71+
right = mid;
72+
} else {
73+
left = mid + 1;
74+
}
7575
}
76-
return false;
76+
return matrix[left / n][left % n] == target;
7777
}
7878
}
7979
```
@@ -85,15 +85,17 @@ class Solution {
8585
public:
8686
bool searchMatrix(vector<vector<int>>& matrix, int target) {
8787
int m = matrix.size(), n = matrix[0].size();
88-
int l = 0, h = m * n - 1;
89-
while (l <= h) {
90-
int mid = l + ((h - l) >> 1);
88+
int left = 0, right = m * n - 1;
89+
while (left < right) {
90+
int mid = left + right >> 1;
9191
int x = mid / n, y = mid % n;
92-
if (matrix[x][y] == target) return true;
93-
if (matrix[x][y] < target) l = mid + 1;
94-
else h = mid - 1;
92+
if (matrix[x][y] >= target) {
93+
right = mid;
94+
} else {
95+
left = mid + 1;
96+
}
9597
}
96-
return false;
98+
return matrix[left / n][left % n] == target;
9799
}
98100
};
99101
```
@@ -106,28 +108,44 @@ public:
106108
* @param {number} target
107109
* @return {boolean}
108110
*/
109-
var searchMatrix = function (matrix, target) {
110-
const m = matrix.length;
111-
const n = matrix[0].length;
112-
let l = 0;
113-
let h = m * n - 1;
114-
while (l <= h) {
115-
const mid = (l + h) >>> 1;
116-
const x = Math.floor(mid / n);
117-
const y = mid % n;
118-
if (matrix[x][y] == target) {
119-
return true;
120-
}
121-
if (matrix[x][y] < target) {
122-
l = mid + 1;
123-
} else {
124-
h = mid - 1;
111+
var searchMatrix = function(matrix, target) {
112+
const m = matrix.length;
113+
const n = matrix[0].length;
114+
let left = 0;
115+
let right = m * n - 1;
116+
while (left < right) {
117+
const mid = (left + right) >> 1;
118+
const x = Math.floor(mid / n);
119+
const y = mid % n;
120+
if (matrix[x][y] >= target) {
121+
right = mid;
122+
} else {
123+
left = mid + 1;
124+
}
125125
}
126-
}
127-
return false;
126+
return matrix[Math.floor(left / n)][left % n] == target;
128127
};
129128
```
130129

130+
### **Go**
131+
132+
```go
133+
func searchMatrix(matrix [][]int, target int) bool {
134+
m, n := len(matrix), len(matrix[0])
135+
left, right := 0, m*n-1
136+
for left < right {
137+
mid := (left + right) >> 1
138+
x, y := mid/n, mid%n
139+
if matrix[x][y] >= target {
140+
right = mid
141+
} else {
142+
left = mid + 1
143+
}
144+
}
145+
return matrix[left/n][left%n] == target
146+
}
147+
```
148+
131149
### **...**
132150

133151
```

‎solution/0000-0099/0074.Search a 2D Matrix/Solution.cpp

Lines changed: 9 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -2,14 +2,16 @@ class Solution {
22
public:
33
bool searchMatrix(vector<vector<int>>& matrix, int target) {
44
int m = matrix.size(), n = matrix[0].size();
5-
int l = 0, h = m * n - 1;
6-
while (l <= h) {
7-
int mid = l + ((h - l) >> 1);
5+
int left = 0, right = m * n - 1;
6+
while (left < right) {
7+
int mid = left + right >> 1;
88
int x = mid / n, y = mid % n;
9-
if (matrix[x][y] == target) return true;
10-
if (matrix[x][y] < target) l = mid + 1;
11-
else h = mid - 1;
9+
if (matrix[x][y] >= target) {
10+
right = mid;
11+
} else {
12+
left = mid + 1;
13+
}
1214
}
13-
return false;
15+
return matrix[left / n][left % n] == target;
1416
}
1517
};

‎solution/0000-0099/0074.Search a 2D Matrix/Solution.go

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
func searchMatrix(matrix [][]int, target int) bool {
2+
m, n := len(matrix), len(matrix[0])
3+
left, right := 0, m*n-1
4+
for left < right {
5+
mid := (left + right) >> 1
6+
x, y := mid/n, mid%n
7+
if matrix[x][y] >= target {
8+
right = mid
9+
} else {
10+
left = mid + 1
11+
}
12+
}
13+
return matrix[left/n][left%n] == target
14+
}

‎solution/0000-0099/0074.Search a 2D Matrix/Solution.java

Lines changed: 9 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1,14 +1,16 @@
11
class Solution {
22
public boolean searchMatrix(int[][] matrix, int target) {
33
int m = matrix.length, n = matrix[0].length;
4-
int l = 0, h = m * n - 1;
5-
while (l <= h) {
6-
int mid = (l + h) >>> 1;
4+
int left = 0, right = m * n - 1;
5+
while (left < right) {
6+
int mid = (left + right) >> 1;
77
int x = mid / n, y = mid % n;
8-
if (matrix[x][y] == target) return true;
9-
if (matrix[x][y] < target) l = mid + 1;
10-
else h = mid - 1;
8+
if (matrix[x][y] >= target) {
9+
right = mid;
10+
} else {
11+
left = mid + 1;
12+
}
1113
}
12-
return false;
14+
return matrix[left / n][left % n] == target;
1315
}
1416
}

‎solution/0000-0099/0074.Search a 2D Matrix/Solution.js

Lines changed: 13 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -3,23 +3,20 @@
33
* @param {number} target
44
* @return {boolean}
55
*/
6-
var searchMatrix = function (matrix, target) {
6+
var searchMatrix = function(matrix, target) {
77
const m = matrix.length;
88
const n = matrix[0].length;
9-
let l = 0;
10-
let h = m * n - 1;
11-
while (l <= h) {
12-
const mid = (l + h) >>> 1;
13-
const x = Math.floor(mid / n);
14-
const y = mid % n;
15-
if (matrix[x][y] == target) {
16-
return true;
17-
}
18-
if (matrix[x][y] < target) {
19-
l = mid + 1;
20-
} else {
21-
h = mid - 1;
22-
}
9+
let left = 0;
10+
let right = m * n - 1;
11+
while (left < right) {
12+
const mid = (left + right + 1) >> 1;
13+
const x = Math.floor(mid / n);
14+
const y = mid % n;
15+
if (matrix[x][y] <= target) {
16+
left = mid;
17+
} else {
18+
right = mid - 1;
19+
}
2320
}
24-
return false;
21+
return matrix[Math.floor(left / n)][left % n] == target;
2522
};

0 commit comments

Comments
 (0)