Skip to content

Commit dd8d880

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lc problem: No.1337. The K Weakest Rows in a Matrix
1 parent beeca1c commit dd8d880

File tree

4 files changed

+133
-4
lines changed

4 files changed

+133
-4
lines changed

‎solution/1300-1399/1337.The K Weakest Rows in a Matrix/README.md

Lines changed: 45 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -73,22 +73,65 @@ k = 2
7373

7474
<!-- 这里可写通用的实现逻辑 -->
7575

76+
二分查找 + 排序。
77+
7678
<!-- tabs:start -->
7779

7880
### **Python3**
7981

8082
<!-- 这里可写当前语言的特殊实现逻辑 -->
8183

8284
```python
83-
85+
class Solution:
86+
def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
87+
m, n = len(mat), len(mat[0])
88+
res = []
89+
for row in mat:
90+
left, right = 0, n
91+
while left < right:
92+
mid = (left + right) >> 1
93+
if row[mid] == 0:
94+
right = mid
95+
else:
96+
left = mid + 1
97+
res.append(left)
98+
idx = list(range(m))
99+
idx.sort(key=lambda x: res[x])
100+
return idx[:k]
84101
```
85102

86103
### **Java**
87104

88105
<!-- 这里可写当前语言的特殊实现逻辑 -->
89106

90107
```java
91-
108+
class Solution {
109+
public int[] kWeakestRows(int[][] mat, int k) {
110+
int m = mat.length, n = mat[0].length;
111+
int[] res = new int[m];
112+
List<Integer> idx = new ArrayList<>();
113+
for (int i = 0; i < m; ++i) {
114+
idx.add(i);
115+
int[] row = mat[i];
116+
int left = 0, right = n;
117+
while (left < right) {
118+
int mid = (left + right) >> 1;
119+
if (row[mid] == 0) {
120+
right = mid;
121+
} else {
122+
left = mid + 1;
123+
}
124+
}
125+
res[i] = left;
126+
}
127+
idx.sort(Comparator.comparingInt(a -> res[a]));
128+
int[] ans = new int[k];
129+
for (int i = 0; i < k; ++i) {
130+
ans[i] = idx.get(i);
131+
}
132+
return ans;
133+
}
134+
}
92135
```
93136

94137
### **...**

‎solution/1300-1399/1337.The K Weakest Rows in a Matrix/README_EN.md

Lines changed: 45 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -70,18 +70,61 @@ The rows ordered from weakest to strongest are [0,2,3,1].
7070

7171
## Solutions
7272

73+
Binary search & sort.
74+
7375
<!-- tabs:start -->
7476

7577
### **Python3**
7678

7779
```python
78-
80+
class Solution:
81+
def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
82+
m, n = len(mat), len(mat[0])
83+
res = []
84+
for row in mat:
85+
left, right = 0, n
86+
while left < right:
87+
mid = (left + right) >> 1
88+
if row[mid] == 0:
89+
right = mid
90+
else:
91+
left = mid + 1
92+
res.append(left)
93+
idx = list(range(m))
94+
idx.sort(key=lambda x: res[x])
95+
return idx[:k]
7996
```
8097

8198
### **Java**
8299

83100
```java
84-
101+
class Solution {
102+
public int[] kWeakestRows(int[][] mat, int k) {
103+
int m = mat.length, n = mat[0].length;
104+
int[] res = new int[m];
105+
List<Integer> idx = new ArrayList<>();
106+
for (int i = 0; i < m; ++i) {
107+
idx.add(i);
108+
int[] row = mat[i];
109+
int left = 0, right = n;
110+
while (left < right) {
111+
int mid = (left + right) >> 1;
112+
if (row[mid] == 0) {
113+
right = mid;
114+
} else {
115+
left = mid + 1;
116+
}
117+
}
118+
res[i] = left;
119+
}
120+
idx.sort(Comparator.comparingInt(a -> res[a]));
121+
int[] ans = new int[k];
122+
for (int i = 0; i < k; ++i) {
123+
ans[i] = idx.get(i);
124+
}
125+
return ans;
126+
}
127+
}
85128
```
86129

87130
### **...**

‎solution/1300-1399/1337.The K Weakest Rows in a Matrix/Solution.java

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
class Solution {
2+
public int[] kWeakestRows(int[][] mat, int k) {
3+
int m = mat.length, n = mat[0].length;
4+
int[] res = new int[m];
5+
List<Integer> idx = new ArrayList<>();
6+
for (int i = 0; i < m; ++i) {
7+
idx.add(i);
8+
int[] row = mat[i];
9+
int left = 0, right = n;
10+
while (left < right) {
11+
int mid = (left + right) >> 1;
12+
if (row[mid] == 0) {
13+
right = mid;
14+
} else {
15+
left = mid + 1;
16+
}
17+
}
18+
res[i] = left;
19+
}
20+
idx.sort(Comparator.comparingInt(a -> res[a]));
21+
int[] ans = new int[k];
22+
for (int i = 0; i < k; ++i) {
23+
ans[i] = idx.get(i);
24+
}
25+
return ans;
26+
}
27+
}

‎solution/1300-1399/1337.The K Weakest Rows in a Matrix/Solution.py

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
class Solution:
2+
def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
3+
m, n = len(mat), len(mat[0])
4+
res = []
5+
for row in mat:
6+
left, right = 0, n
7+
while left < right:
8+
mid = (left + right) >> 1
9+
if row[mid] == 0:
10+
right = mid
11+
else:
12+
left = mid + 1
13+
res.append(left)
14+
idx = list(range(m))
15+
idx.sort(key=lambda x: res[x])
16+
return idx[:k]

0 commit comments

Comments
 (0)