1337_The_K_Weakest_Rows_in_a_Matrix

qiyuangong · qiyuangong · commit 85132d6b6db5 · 2020-02-23T21:49:27.000+08:00
diff --git a/README.md b/README.md
@@ -218,6 +218,7 @@ Also, there are open source implementations for basic data structs and algorithm
 | 973 | [K Closest Points to Origin](https://leetcode.com/problems/k-closest-points-to-origin/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/973_K_Closest_Points_to_Origin.py) [Java](https://github.com/qiyuangong/leetcode/blob/master/java/973_K_Closest_Points_to_Origin.java) | 1. Sort and get 0-K, O(nlogn) and O(1)<br>2. Min Heap, O(nlogk) and O(k) |
 | 1064 | [Fixed Point](https://leetcode.com/problems/fixed-point/) &hearts; | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/1064_Fixed_Point.py) [Java](https://github.com/qiyuangong/leetcode/blob/master/java/1064_Fixed_Point.java) | 1. Go through index and value, until find solution encounter index < value, O(n) and O(1)<br>2. Binary search, O(logn) and O(1) |
 | 1260 | [Shift 2D Grid](https://leetcode.com/problems/shift-2d-grid/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/1260_Shift_2D_Grid.py) [Java](https://github.com/qiyuangong/leetcode/blob/master/java/1260_Shift_2D_Grid.java) | Final position of each element can be computed according to k, m and n, e.g., k == mn, then don't move, O(mn) and O(mn) |
+| 1337 | [The K Weakest Rows in a Matrix](https://leetcode.com/problems/the-k-weakest-rows-in-a-matrix/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/1337_The_K_Weakest_Rows_in_a_Matrix.py) [Java](https://github.com/qiyuangong/leetcode/blob/master/java/1337_The_K_Weakest_Rows_in_a_Matrix.java) | Check by row, from left to right, until encount first zero, O(mn) and O(1) |
 
 | # | To Understand |
 |---| ----- |
diff --git a/java/1337_The_K_Weakest_Rows_in_a_Matrix.java b/java/1337_The_K_Weakest_Rows_in_a_Matrix.java
@@ -0,0 +1,30 @@
+class Solution {
+    public int[] kWeakestRows(int[][] mat, int k) {
+        List<Integer> res = new ArrayList<>();
+        int col = 0;
+        boolean flag = true;
+        while (col < mat[0].length && flag) {
+            for (int i = 0; i < mat.length; i++) {
+                if (res.contains(i)) continue;
+                // Add first row with 0 into res
+                if (mat[i][col] == 0) res.add(i);
+                if (res.size() == k) {
+                    flag = false;
+                    break;
+                }
+            }
+            col += 1;
+        }
+        if (flag) {
+            // if res less than k
+            for (int i = 0; i < mat.length; i++) {
+                if (res.contains(i)) continue;
+                res.add(i);
+                if (res.size() == k) break;
+            }
+        }
+        int[] ret = new int[k];
+        for (int i = 0; i < k; i++) ret[i] = res.get(i);
+        return ret;
+    }
+}
diff --git a/python/1337_The_K_Weakest_Rows_in_a_Matrix.py b/python/1337_The_K_Weakest_Rows_in_a_Matrix.py
@@ -0,0 +1,33 @@
+class Solution(object):
+    def kWeakestRows(self, mat, k):
+        """
+        :type mat: List[List[int]]
+        :type k: int
+        :rtype: List[int]
+        """
+        res = []
+        num_row = len(mat)
+        num_col = len(mat[0])
+        col = 0
+        flag = 1
+        while col < num_col and flag:
+            for i in range(num_row):
+                if i in res:
+                    continue
+                # Add first row with 0 into res
+                if mat[i][col] == 0:
+                    res.append(i)
+                if len(res) == k:
+                    flag = 0
+                    break
+            col += 1
+        if len(res) == k:
+            return res
+        # if res less than k
+        for i in range(num_row):
+            if i in res:
+                continue
+            res.append(i)
+            if len(res) == k:
+                break
+        return res
