目录
题目要求
思路：模拟
- 遍历每列每个数，判断顺序即可；
- 后者小于前者则结果（要删除的列）加一，跳出当前列的循环。
Java
class Solution {
public int minDeletionSize(String[] strs) {
int n = strs.length, m = strs[0].length(), res = 0;
for(int c = 0; c < m; ++c) {
for(int r = 1; r < n; ++r) {
if(strs[r - 1].charAt(c) > strs[r].charAt(c)) { // 后者小于前者
res++;
break;
}
}
}
return res;
}
}
- 时间复杂度：
O
(
m
×
n
)
O(mtimes n)
O(m×n)
- 空间复杂度：
O
(
1
)
O(1)
O(1)
C++
class Solution {
public:
int minDeletionSize(vector& strs) {
int n = strs.size(), m = strs[0].size(), res = 0;
for(int c = 0; c < m; ++c) {
for(int r = 1; r < n; ++r) {
if(strs[r - 1][c] > strs[r][c]) { // 后者小于前者
res++;
break;
}
}
}
return res;
}
};
- 时间复杂度：
O
(
m
×
n
)
O(mtimes n)
O(m×n)
- 空间复杂度：
O
(
1
)
O(1)
O(1)
Rust
impl Solution {
pub fn min_deletion_size(strs: Vec) -> i32 {
let mut res = 0;
let arr = strs.iter().map(|s| s.chars().collect::>()).collect::>(); //似乎是用来转为可访问的数组？
for c in 0..strs[0].len() {
for r in 1..strs.len() {
if arr[r - 1][c] > arr[r][c] { // 后者小于前者
res += 1;
break;
}
}
}
res
}
}
- 时间复杂度：
O
(
m
×
n
)
O(mtimes n)
O(m×n)
- 空间复杂度：
O
(
1
)
O(1)
O(1)
总结
是久违的模拟简单题，快乐cv一波rust。
