1337. 矩陣中戰斗力最弱的 K 行（C++）
- 1 題目描述
- 2 示例描述
- 2.1 示例1
- 2.2 示例2
- 3 解題提示
- 4 解題思路
- 5 原始碼詳解（C++）
- 6 錯誤思路
- 7 原始碼詳解（C++）
1 題目描述
給你一個大小為 m * n 的矩陣 mat，矩陣由若干軍人和平民組成，分別用 1 和 0 表示，
請你回傳矩陣中戰斗力最弱的 k 行的索引，按從最弱到最強排序，
如果第 i 行的軍人數量少于第 j 行，或者兩行軍人數量相同但 i 小于 j，那么我們認為第 i 行的戰斗力比第 j 行弱，
軍人 總是 排在一行中的靠前位置，也就是說 1 總是出現在 0 之前，
2 示例描述
2.1 示例1
輸入：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
輸出：[2,0,3]
解釋：
每行中的軍人數目：
行 0 -> 2
行 1 -> 4
行 2 -> 1
行 3 -> 2
行 4 -> 5
從最弱到最強對這些行排序后得到 [2,0,3,1,4]
2.2 示例2
輸入：mat =
[[1,0,0,0],
[1,1,1,1],
[1,0,0,0],
[1,0,0,0]],
k = 2
輸出：[0,2]
解釋：
每行中的軍人數目：
行 0 -> 1
行 1 -> 4
行 2 -> 1
行 3 -> 1
從最弱到最強對這些行排序后得到 [0,2,3,1]
3 解題提示
m == mat.length
n == mat[i].length
2 <= n, m <= 100
1 <= k <= m
matrix[i][j] 不是 0 就是 1
4 解題思路
暴力求解
5 原始碼詳解（C++）
class Solution {
public:
vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
int sum[100] = { 0 };
vector<int> res ;
for ( int i = 0 ; i < mat.size() ; i ++ )
{
for ( int j = 0 ; j < mat[i].size() ; j ++ )
{
sum[i] = sum[i] + mat[i][j] ;
}
}
for ( int i = 0 ; i <= mat[0].size() ; i ++ )
{
for ( int j = 0 ; j < mat.size() ; j ++ )
{
if ( sum[j] == i )
{
res.push_back( j ) ;
if ( res.size() == k )
{
return res ;
}
}
}
}
return { 0 } ;
}
};
6 錯誤思路
更好理解的暴力求解，
7 原始碼詳解（C++）
class Solution {
public:
vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
int n[100] = { 0 } , sum = 0 ;
for ( int i = 0 ; i < mat.size() ; i ++ )
{
sum = 0 ;
for ( int j = 0 ; j < mat[i].size() ; j ++ )
{
sum = sum + mat[i][j] ;
}
n[i] = sum ;
}
vector<int> index ;
for ( int i = 0 ; i < mat.size() -1 ; i ++ )
{
if ( n[i] <= n[i + 1] )
{
index.push_back( i ) ;
}
}
//轉換到陣列排排序，留兩個陣列，一個是數值，一個是下標，
int count = index.size() ;
int number[100] = { 0 } , arr_index[100] = { 0 } ;
for ( int i = 0 ; i < index.size() ; i ++ )
{
number[i] = n[index[i]] ;
arr_index[i] = index[i] ;
}
//排序
int temp = 0 ;
for ( int i = 0 ; i < index.size() - 1 ; i ++ )
{
for ( int j = i + 1 ; j < index.size() ; j ++ )
{
if ( number[i] < number[j] )
{
//交換數字
temp = number[i] ;
number[i] = number[j] ;
number[j] = temp ;
//交換下標
temp = arr_index[i] ;
arr_index[i] = arr_index[j] ;
arr_index[j] = temp ;
}
}
}
for ( int i = 0 ; i < index.size() ; i ++ )
{
index.push_back( arr_index[i] ) ;
}
return index ;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/266017.html
標籤：其他
上一篇：C語言 | 學習使用異或^
下一篇：Mybatis第一次課