包含相等值数字块的数量
难度:
标签:
题目描述
代码结果
运行时间: 587 ms, 内存: 47.7 MB
// 题目思路:
// 使用Java Stream对数组进行处理。首先,将数组转换为流,
// 然后通过滑动窗口检查相邻元素是否相等。
// 最后,统计块的数量。
import java.util.stream.IntStream;
import java.util.stream.Collectors;
import java.util.List;
public class EqualValueBlocksStream {
public long countEqualValueBlocks(int[] nums) {
if (nums.length == 0) return 0;
List<Integer> list = IntStream.of(nums).boxed().collect(Collectors.toList());
long count = IntStream.range(1, nums.length)
.filter(i -> !list.get(i).equals(list.get(i - 1)))
.count();
return count + 1;
}
public static void main(String[] args) {
EqualValueBlocksStream solution = new EqualValueBlocksStream();
int[] nums = {1, 2, 2, 3, 3, 3, 4};
System.out.println(solution.countEqualValueBlocks(nums)); // 输出: 4
}
}
解释
方法:
此题解的核心思路是遍历数组,使用两个指针来标记和计算连续相同元素的块。具体地,使用一个外部循环遍历数组,内部使用二分搜索(通过`bisect_left`)来快速跳过当前块的所有相同元素。`bisect_left`的用途是找到第一个与当前元素不同的位置,从而更新外部循环的指针。每完成一个块的统计,结果计数器`res`增加1。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
在解题中使用`bisect_left`配合lambda函数来跳过相同元素,这种方法在什么情况下效率最高?
▷🦆
如果数组`nums`中包含非常多的连续相等的数字块,这种方法的时间复杂度如何变化?
▷🦆
在你的算法中,为什么选择在`range(i, n)`上应用`bisect_left`而不是简单地使用循环来找到下一个不同的元素?
▷