You are given an m x n binary matrix mat of 1's (representing soldiers) and 0's (representing civilians). The soldiers are positioned in front of the civilians. That is, all the 1's will appear to the left of all the 0's in each row.
A row i is weaker than a row j if one of the following is true:
i is less than the number of soldiers in row j.i < j.Return the indices of the k weakest rows in the matrix ordered from weakest to strongest.
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 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].
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 in each row is: - Row 0: 1 - Row 1: 4 - Row 2: 1 - Row 3: 1 The rows ordered from weakest to strongest are [0,2,3,1].
Constraints:
m == mat.lengthn == mat[i].length2 <= n, m <= 1001 <= k <= mmatrix[i][j] is either 0 or 1.program main
implicit none
integer, parameter :: m = 5, n = 5
integer, dimension(m, n) :: mat
integer :: i, j, k
integer, dimension(:), allocatable :: weakest_rows
! Example 1
mat = reshape([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], shape(mat))
k = 3
call solve(mat, k, weakest_rows)
write (*, '(*(I0, 1X))') weakest_rows
! Example 2
mat = reshape([1, 0, 0, 0, &
1, 1, 1, 1, &
1, 0, 0, 0, &
1, 0, 0, 0], shape(mat))
k = 2
call solve(mat, k, weakest_rows)
write (*, '(*(I0, 1X))') weakest_rows
contains
subroutine solve(mat, k, weakest_rows)
implicit none
integer, intent(in) :: m, n, k
integer, dimension(m, n), intent(in) :: mat
integer, dimension(:), allocatable, intent(out) :: weakest_rows
integer :: i, j, num_soldiers, min_num_soldiers, min_row_index
allocate(weakest_rows(k))
do i = 1, m
num_soldiers = count(mat(i, :) == 1)
if (i == 1 .or. num_soldiers < min_num_soldiers) then
min_num_soldiers = num_soldiers
min_row_index = i
end if
end do
weakest_rows(1) = min_row_index
do i = 2, k
min_row_index = 1
min_num_soldiers = mat(1, :)
do j = 2, m
if ((mat(j, :) < min_num_soldiers) .or. &
(mat(j, :) == min_num_soldiers .and. j < min_row_index)) then
min_num_soldiers = mat(j, :)
min_row_index = j
end if
end do
weakest_rows(i) = min_row_index
end do
end subroutine solve
end program maintemp.f95:33:27:
33 | integer, dimension(m, n), intent(in) :: mat
| 1
Error: Variable ‘m’ cannot appear in the expression at (1)
temp.f95:32:32:
32 | integer, intent(in) :: m, n, k
| 1
Error: Symbol at (1) is not a DUMMY variable
temp.f95:33:29:
33 | integer, dimension(m, n), intent(in) :: mat
| 1
Error: Variable ‘n’ cannot appear in the expression at (1)
temp.f95:32:35:
32 | integer, intent(in) :: m, n, k
| 1
Error: Symbol at (1) is not a DUMMY variable
temp.f95:50:12:
50 | min_num_soldiers = mat(1, :)
| 1
Error: Incompatible ranks 0 and 1 in assignment at (1)
temp.f95:52:55:
52 | if ((mat(j, :) < min_num_soldiers) .or. &
| 1
Error: IF clause at (1) requires a scalar LOGICAL expression
temp.f95:54:20:
54 | min_num_soldiers = mat(j, :)
| 1
Error: Incompatible ranks 0 and 1 in assignment at (1)
temp.f95:20:18:
20 | mat = reshape([1, 0, 0, 0, &
| 1
Error: Without padding, there are not enough elements in the intrinsic RESHAPE source at (1) to match the shape
module weakest_rows
implicit none
contains
subroutine solve(mat, m, n, k, indices)
integer, intent(in) :: m, n, k
integer, intent(in) :: mat(m, n)
integer, intent(out) :: indices(k)
! Local variables
integer :: i, j, count, weakest_row
integer :: soldiers(m), civilians(m)
! Initialize variables
count = 0
weakest_row = 1
! Count the number of soldiers and civilians in each row
do i = 1, m
soldiers(i) = 0
civilians(i) = 0
do j = 1, n
if (mat(i, j) == 1) then
soldiers(i) = soldiers(i) + 1
else
civilians(i) = civilians(i) + 1
end if
end do
end do
! Find the weakest rows
do i = 1, m
if (soldiers(i) < k .or. (soldiers(i) == k .and. i < weakest_row)) then
count = count + 1
indices(count) = i
if (count == k) exit
end if
end do
! If there are less than k weakest rows, add the remaining rows
if (count < k) then
do i = weakest_row, m
if (soldiers(i) < k .or. (soldiers(i) == k .and. i < weakest_row)) then
count = count + 1
indices(count) = i
if (count == k) exit
end if
end do
end if
end subroutine solve
end module weakest_rows
program main
use weakest_rows
implicit none
integer, parameter :: m = 5, n = 5, k = 3
integer :: mat(m, n)
integer :: indices(k)
! Example 1
mat = reshape((/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/), shape(mat))
call solve(mat, m, n, k, indices)
write (*, *) indices
! Example 2
mat = reshape((/1, 0, 0, 0, &
1, 1, 1, 1, &
1, 0, 0, 0, &
1, 0, 0, 0/), shape(mat))
call solve(mat, m, n, k, indices)
write (*, *) indices
end program main
temp.f95:68:16:
68 | mat = reshape((/1, 0, 0, 0, &
| 1
Error: Without padding, there are not enough elements in the intrinsic RESHAPE source at (1) to match the shape
from typing import List
def kWeakestRows(mat: List[List[int]], k: int) -> List[int]:
soldiers_count = [(sum(row), idx) for idx, row in enumerate(mat)]
soldiers_count.sort()
return [x[1] for x in soldiers_count[:k]]
#include <vector>
#include <algorithm>
using namespace std;
vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
vector<pair<int, int>> soldiersCount;
for (int i = 0; i < mat.size(); ++i) {
int cnt = count(mat[i].begin(), mat[i].end(), 1);
soldiersCount.push_back({cnt, i});
}
sort(soldiersCount.begin(), soldiersCount.end());
vector<int> result(k);
for (int i = 0; i < k; ++i) {
result[i] = soldiersCount[i].second;
}
return result;
}