Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1337.html

1337. The K Weakest Rows in a Matrix

Level

Easy

Description

Given a m * n matrix mat of ones (representing soldiers) and zeros (representing civilians), return the indexes of the k weakest rows in the matrix ordered from the weakest to the strongest.

A row i is weaker than row j, if the number of soldiers in row i is less than the number of soldiers in row j, or they have the same number of soldiers but i is less than j. Soldiers are always stand in the frontier of a row, that is, always ones may appear first and then zeros.

Example 1:

Input: mat = 
[[1,1,0,0,0],
 [1,1,1,1,0],
 [1,0,0,0,0],
 [1,1,0,0,0],
 [1,1,1,1,1]], 
k = 3
Output: [2,0,3]
Explanation: 
The number of soldiers for each row is: 
row 0 -> 2 
row 1 -> 4 
row 2 -> 1 
row 3 -> 2 
row 4 -> 5 
Rows ordered from the weakest to the strongest are [2,0,3,1,4]

Example 2:

Input: mat = 
[[1,0,0,0],
 [1,1,1,1],
 [1,0,0,0],
 [1,0,0,0]], 
k = 2
Output: [0,2]
Explanation: 
The number of soldiers for each row is: 
row 0 -> 1 
row 1 -> 4 
row 2 -> 1 
row 3 -> 1 
Rows ordered from the weakest to the strongest are [0,2,3,1]

Constraints:

  • m == mat.length
  • n == mat[i].length
  • 2 <= n, m <= 100
  • 1 <= k <= m
  • matrix[i][j] is either 0 or 1.

Solution

For each row in mat, obtain the number of soldiers. Use a 2D array to store each row’s index and the number of soldiers. Sort the 2D array according to the number of soldiers in ascending order then according to the indices in ascending order. After sorting, use an array to store the indices of the first k rows, and return.

  • class Solution {
    public int[] kWeakestRows(int[][] mat, int k) {
        if (mat == null || mat.length == 0 || mat[0].length == 0)
            return new int[0];
        int rows = mat.length, columns = mat[0].length;
        int[][] indexCount = new int[rows][2];
        for (int i = 0; i < rows; i++) {
            int rowCount = 0;
            for (int j = 0; j < columns; j++) {
                if (mat[i][j] == 1)
                    rowCount++;
                else
                    break;
            }
            indexCount[i][0] = i;
            indexCount[i][1] = rowCount;
        }
        Arrays.sort(indexCount, new Comparator<int[]>() {
            public int compare(int[] array1, int[] array2) {
                if (array1[1] != array2[1])
                    return array1[1] - array2[1];
                else
                    return array1[0] - array2[0];
            }
        });
        int[] kWeakest = new int[k];
        for (int i = 0; i < k; i++)
            kWeakest[i] = indexCount[i][0];
        return kWeakest;
    }
}

  • // OJ: https://leetcode.com/problems/the-k-weakest-rows-in-a-matrix/
// Time: O(MlogN + MlogM)
// Space: O(M)
class Solution {
public:
    vector<int> kWeakestRows(vector<vector<int>>& A, int k) {
        vector<pair<int, int>> B;
        int M = A.size(), N = A[0].size();
        for (int i = 0; i < M; ++i) {
            int L = 0, R = N - 1;
            while (L <= R) {
                int M = (L + R) / 2;
                if (A[i][M] == 1) L = M + 1;
                else R = M - 1;
            }
            B.emplace_back(R, i);
        }
        sort(begin(B), end(B));
        vector<int> ans;
        for (int i = 0; i < k; ++i) ans.push_back(B[i].second);
        return ans;
    }
};

  • class Solution:
    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
        m, n = len(mat), len(mat[0])
        ans = [n - bisect_right(row[::-1], 0) for row in mat]
        idx = list(range(m))
        idx.sort(key=lambda i: ans[i])
        return idx[:k]



  • func kWeakestRows(mat [][]int, k int) []int {
	m, n := len(mat), len(mat[0])
	res := make([]int, m)
	var idx []int
	for i, row := range mat {
		idx = append(idx, i)
		left, right := 0, n
		for left < right {
			mid := (left + right) >> 1
			if row[mid] == 0 {
				right = mid
			} else {
				left = mid + 1
			}
		}
		res[i] = left
	}
	sort.Slice(idx, func(i, j int) bool {
		return res[idx[i]] < res[idx[j]] || (res[idx[i]] == res[idx[j]] && idx[i] < idx[j])
	})
	return idx[:k]
}

  • function kWeakestRows(mat: number[][], k: number): number[] {
    let n = mat.length;
    let sumMap = mat.map((d, i) => [d.reduce((a, c) => a + c, 0), i]);
    let ans = [];
    // 冒泡排序
    for (let i = 0; i < k; i++) {
        for (let j = i; j < n; j++) {
            if (
                sumMap[j][0] < sumMap[i][0] ||
                (sumMap[j][0] == sumMap[i][0] && sumMap[i][1] > sumMap[j][1])
            ) {
                [sumMap[i], sumMap[j]] = [sumMap[j], sumMap[i]];
            }
        }
        ans.push(sumMap[i][1]);
    }
    return ans;
}

All Problems

All Solutions