Algorithm - the K row with the weakest combat power in the matrix (kotlin)

subject

Give you a size of m * n Matrix mat, The matrix consists of a number of soldiers and civilians , Use them separately 1 and 0 Express .

Please return to the weakest in the matrix k Index of rows , Sort by weakest to strongest .

If the first i The number of soldiers in line is less than the number of j That's ok , Or two lines of soldiers in the same number but i Less than j, So we think the i The battle effectiveness of the line is better than the first j Row weakness .

Soldiers Always The front position in a row , in other words 1 Always in 0 Before .

 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]
 explain ：
 The number of soldiers in each line ：
 That's ok  0 -> 2 
 That's ok  1 -> 4 
 That's ok  2 -> 1 
 That's ok  3 -> 2 
 That's ok  4 -> 5 
 Sort these rows from the weakest to the strongest to get  [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]
 explain ： 
 The number of soldiers in each line ：
 That's ok  0 -> 1 
 That's ok  1 -> 4 
 That's ok  2 -> 1 
 That's ok  3 -> 1 
 Sort these rows from the weakest to the strongest to get  [0,2,3,1]
 

Tips ：

m == mat.length
n == mat[i].length
2 <= n, m <= 100
1 <= k <= m
matrix[i][j] No 0 Namely 1

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/the-k-weakest-rows-in-a-matrix
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

resolvent

    fun kWeakestRows(mat: Array<IntArray>, k: Int): IntArray {
    
        var pair = Array(mat.size) {
     Array(2) {
     0 } }
        mat.forEachIndexed {
     index, ints ->
            run {
    
                pair[index][0] = index
                mat[index].forEach {
    
                    pair[index][1] += it
                }
            }
        }

        Arrays.sort(pair,0,pair.size) {
     o1, o2 -> if (o1[1] > o2[1]) 1 else if (o1[1] == o2[1]) 0 else -1 }

        val result = IntArray(k) {
     0 }

        for (i in 0 until k){
    
            result[i] = pair[i][0]
        }
        return result
    }

summary

1. Because soldiers are always ahead , So you can also index Judge the combat effectiveness of the current row , Dichotomy is faster to find the maximum combat effectiveness , Not all of them