1337. The K Weakest Rows in a Matrix

leetcode easy

#array#csharp#easy#leetcode#matrix#sort#string

Task

Вам дана бинарная матрица размером m x n mat, состоящая из 1 (представляющих солдат) и 0 (представляющих гражданских лиц). Солдаты расположены перед гражданскими лицами. То есть, все 1 будут расположены слева от всех 0 в каждой строке.

Строка i слабее строки j, если выполнено одно из следующих условий:

Количество солдат в строке i меньше, чем в строке j.

Обе строки имеют одинаковое количество солдат, но i < j.

Верните индексы k самых слабых строк в матрице, упорядоченных от самой слабой к самой сильной.

Пример:

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 in each row is:

- Row 0: 2

- Row 1: 4

- Row 2: 1

- Row 3: 2

- Row 4: 5

The rows ordered from weakest to strongest are [2,0,3,1,4].

C# solution

matched/original

public class Solution {
    public int[] KWeakestRows(int[][] mat, int k) {
        int m = mat.Length;
        int n = mat[0].Length;
        var pairs = new List<(int strength, int index)>();
        for (int i = 0; i < m; i++) {
            int strength = 0;
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) break;
                strength++;
            }
            pairs.Add((strength, i));
        }
        pairs.Sort((a, b) => {
            if (a.strength == b.strength) return a.index - b.index;
            return a.strength - b.strength;
        });
        int[] indexes = new int[k];
        for (int i = 0; i < k; i++) {
            indexes[i] = pairs[i].index;
        }
        return indexes;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public vector<int>& KWeakestRows(int[][] mat, int k) {
        int m = mat.size();
        int n = mat[0].size();
        var pairs = new List<(int strength, int index)>();
        for (int i = 0; i < m; i++) {
            int strength = 0;
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) break;
                strength++;
            }
            pairs.push_back((strength, i));
        }
        pairs.Sort((a, b) => {
            if (a.strength == b.strength) return a.index - b.index;
            return a.strength - b.strength;
        });
        vector<int>& indexes = new int[k];
        for (int i = 0; i < k; i++) {
            indexes[i] = pairs[i].index;
        }
        return indexes;
    }
}

Java solution

auto-draft, review before submit

import java.util.*;
import java.math.*;

// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
    public int[] KWeakestRows(int[][] mat, int k) {
        int m = mat.length;
        int n = mat[0].length;
        var pairs = new List<(int strength, int index)>();
        for (int i = 0; i < m; i++) {
            int strength = 0;
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) break;
                strength++;
            }
            pairs.add((strength, i));
        }
        pairs.Sort((a, b) => {
            if (a.strength == b.strength) return a.index - b.index;
            return a.strength - b.strength;
        });
        int[] indexes = new int[k];
        for (int i = 0; i < k; i++) {
            indexes[i] = pairs[i].index;
        }
        return indexes;
    }
}

Python solution

matched/original

class Solution:
    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
        m = len(mat)
        n = len(mat[0])

        pairs = []
        for i in range(m):
            strength = 0
            for j in range(n):
                if mat[i][j] == 0:
                    break
                strength += 1
            pairs.append((strength, i))

        pairs.sort()
        indexes = [pairs[i][1] for i in range(k)]
        return indexes

Go solution

matched/original

func kWeakestRows(mat [][]int, k int) []int {
    m := len(mat)
    n := len(mat[0])

    pairs := make([][2]int, m)
    for i := 0; i < m; i++ {
        strength := 0
        for j := 0; j < n; j++ {
            if mat[i][j] == 0 {
                break
            }
            strength++
        }
        pairs[i][0] = strength
        pairs[i][1] = i
    }

    sort.Slice(pairs, func(a, b int) bool {
        if pairs[a][0] == pairs[b][0] {
            return pairs[a][1] < pairs[b][1]
        }
        return pairs[a][0] < pairs[b][0]
    })

    indexes := make([]int, k)
    for i := 0; i < k; i++ {
        indexes[i] = pairs[i][1]
    }
    return indexes
}

Explanation

Algorithm

Вычислите силу каждой строки матрицы и поместите пары сила/индекс в массив. Для каждой строки подсчитайте количество единиц (солдат) до первой нуля (гражданского), чтобы определить силу строки.

Отсортируйте массив пар по возрастанию силы, а в случае равенства силы — по возрастанию индекса. Для этого потребуется реализовать компаратор, который сравнивает сначала силу, а затем индекс.

Извлеките первые k индексов из отсортированного массива и верните их. Эти индексы будут соответствовать k самым слабым строкам в порядке от самой слабой к самой сильной.

😎