删列造序 II
难度:
标签:
题目描述
代码结果
运行时间: 35 ms, 内存: 16.0 MB
/*
* 思路:
* 使用Java Stream进行列的遍历,并检查是否破坏了字典序。
* 如果破坏了,则需要删除这一列。
* 最后返回需要删除的列数。
*/
import java.util.stream.IntStream;
public class Solution {
public int minDeletionSize(String[] strs) {
int n = strs.length;
int m = strs[0].length();
// 统计需要删除的列数
long count = IntStream.range(0, m)
.filter(j -> IntStream.range(1, n)
.anyMatch(i -> strs[i - 1].charAt(j) > strs[i].charAt(j)))
.count();
return (int) count;
}
}
解释
方法:
该题解的思路是:遍历字符串数组每一列,判断当前列是否需要删除。具体做法是,用一个集合 seps 记录当前已经满足字典序的行索引。遍历每一列时,先初始化一个空集合 f,用于记录新增的满足字典序的行索引。然后遍历相邻两行,如果上一行的字符大于下一行,说明不满足字典序,直接将答案加1,并退出当前列的判断;如果上一行的字符小于下一行,则将上一行的索引加入 f 集合。如果内层遍历结束,说明当前列满足字典序,将 f 集合并入 seps。最后返回答案。
时间复杂度:
O(mn)
空间复杂度:
O(m)
代码细节讲解
🦆
在算法中,集合seps和f的具体作用是什么?为什么需要通过这两个集合来跟踪满足字典序的行索引?
▷🦆
算法中提到的'如果上一行的字符大于下一行,则直接将答案加1并退出当前列的判断',这种处理方式是否可能导致忽略某些列在后续行中可能满足字典序的情况?
▷🦆
为什么在内层循环中,只有当上一行字符小于下一行字符时,才将上一行的索引加入到集合f中?当字符相等时,这种情况如何处理?
▷🦆
在算法实现中,为什么选择使用集合而不是其他数据结构,如列表或字典?集合在这里有什么特别的优势?
▷