leetcode
leetcode 2501 ~ 2550
包含相等值数字块的数量

包含相等值数字块的数量

难度:

标签:

题目描述

代码结果

运行时间: 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函数来跳过相同元素,这种方法在什么情况下效率最高?
这种方法效率最高的情况是当数组中存在较长的连续相等元素块时。因为`bisect_left`可以快速地跳过这些连续的相等元素,直接移动到下一个不同的元素,从而减少了不必要的逐一比较和遍历。特别是当块的长度远大于块的数量时,使用二分搜索相比于线性搜索可以显著提高效率。
🦆
如果数组`nums`中包含非常多的连续相等的数字块,这种方法的时间复杂度如何变化?
如果数组中包含许多连续相等的数字块,每个块的长度比较短,这种方法的时间复杂度接近于`O(n log k)`,其中`n`是数组的长度,`k`是最大块的长度。因为`bisect_left`需要在每个块的起始处进行二分搜索,搜索范围最大不超过`k`。当每个块长度很短时,虽然二分搜索相比线性搜索有优势,但频繁的二分搜索调用可能导致效率下降。
🦆
在你的算法中,为什么选择在`range(i, n)`上应用`bisect_left`而不是简单地使用循环来找到下一个不同的元素?
选择使用`bisect_left`而不是简单循环的主要原因是为了提高效率。通过应用二分搜索(`bisect_left`),可以快速找到第一个与当前元素不同的位置,特别是在连续相等元素块较长的情况下,这种方法比线性搜索要快得多。线性搜索虽然简单,但在遇到大量连续相同元素时性能较差。因此,使用`bisect_left`可以在维持算法整体性能的同时,减少不必要的比较次数。

相关问题