Sponsored
Sponsored
In this approach, we directly count the number of soldiers in each row by iterating through the elements of the row, and then sort the rows based on the count followed by their index to determine the order.
Steps to implement:
Time Complexity: O(m*n + m*log m) due to counting and sorting the rows.
Space Complexity: O(m) to store the row strength information.
1#include <vector>
2#include <algorithm>
3using namespace std;
4
5vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
6 vector<pair<int, int>> rowStrength;
7 for (int i = 0; i < mat.size(); ++i) {
8 int soldierCount = 0;
9 for (int j = 0; j < mat[i].size(); ++j) {
10 if (mat[i][j] == 1)
11 soldierCount++;
12 else
13 break;
14 }
15 rowStrength.push_back({soldierCount, i});
16 }
17 sort(rowStrength.begin(), rowStrength.end());
18 vector<int> result;
19 for (int i = 0; i < k; ++i) {
20 result.push_back(rowStrength[i].second);
21 }
22 return result;
23}The C++ code utilizes pairs to store both the count of soldiers in a row and the row index itself. The data is sorted using the built-in sort function, then the indices are extracted for the first 'k' entries in the sorted order.
This approach uses binary search to efficiently count the number of soldiers in each row. Given that soldiers are always positioned before civilians, binary search can help quickly find the first civilian and thus the count of soldiers.
Implementation steps:
Time Complexity: O(m*log n + m*log m) due to binary search for counting and sorting rows.
Space Complexity: O(m), for maintaining strength array storage.
using System.Collections.Generic;
using System.Linq;
public class Solution {
private int CountSoldiers(int[] row) {
int low = 0, high = row.Length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (row[mid] == 1)
low = mid + 1;
else
high = mid - 1;
}
return low;
}
public int[] KWeakestRows(int[][] mat, int k) {
var rowStrength = new List<Tuple<int, int>>();
for (int i = 0; i < mat.Length; i++) {
int soldierCount = CountSoldiers(mat[i]);
rowStrength.Add(new Tuple<int, int>(soldierCount, i));
}
rowStrength.Sort();
return rowStrength.Take(k).Select(x => x.Item2).ToArray();
}
}For C#, the approach of employing a binary search within the Counting of soldiers method mirrors prior techniques, optimizing the evaluation of soldier numbers before results are sorted by traditional List and Tuple operations.