难度: Medium
Submission
运行时间: 587 ms
内存: 47.7 MB
# Definition for BigArray.
# class BigArray:
# def at(self, index: long) -> int:
# pass
# def size(self) -> long:
# pass
class Solution(object):
def countBlocks(self, nums: Optional['BigArray']) -> int:
res,i,n = 0,0,nums.size()
while i<n:
v = nums.at(i)
i+=bisect_left(range(i,n),True,key=lambda x: v!=nums.at(x))
res += 1
return res
Explain
此题解的核心思路是遍历数组，使用两个指针来标记和计算连续相同元素的块。具体地，使用一个外部循环遍历数组，内部使用二分搜索（通过`bisect_left`）来快速跳过当前块的所有相同元素。`bisect_left`的用途是找到第一个与当前元素不同的位置，从而更新外部循环的指针。每完成一个块的统计，结果计数器`res`增加1。
时间复杂度: O(n)
空间复杂度: O(1)
# Definition for BigArray.
# class BigArray:
# def at(self, index: long) -> int:
# pass
# def size(self) -> long:
# pass
class Solution(object):
def countBlocks(self, nums: Optional['BigArray']) -> int:
res, i, n = 0, 0, nums.size() # 初始化结果计数器、索引和数组大小
while i < n: # 外部循环遍历整个数组
v = nums.at(i) # 获取当前元素的值
# 使用bisect_left找到第一个与v不同的元素的索引
i += bisect_left(range(i, n), True, key=lambda x: v != nums.at(x))
res += 1 # 完成一个块的计数，结果+1
return res # 返回总块数
Explore
这种方法效率最高的情况是当数组中存在较长的连续相等元素块时。因为`bisect_left`可以快速地跳过这些连续的相等元素，直接移动到下一个不同的元素，从而减少了不必要的逐一比较和遍历。特别是当块的长度远大于块的数量时，使用二分搜索相比于线性搜索可以显著提高效率。
如果数组中包含许多连续相等的数字块，每个块的长度比较短，这种方法的时间复杂度接近于`O(n log k)`，其中`n`是数组的长度，`k`是最大块的长度。因为`bisect_left`需要在每个块的起始处进行二分搜索，搜索范围最大不超过`k`。当每个块长度很短时，虽然二分搜索相比线性搜索有优势，但频繁的二分搜索调用可能导致效率下降。
选择使用`bisect_left`而不是简单循环的主要原因是为了提高效率。通过应用二分搜索（`bisect_left`），可以快速找到第一个与当前元素不同的位置，特别是在连续相等元素块较长的情况下，这种方法比线性搜索要快得多。线性搜索虽然简单，但在遇到大量连续相同元素时性能较差。因此，使用`bisect_left`可以在维持算法整体性能的同时，减少不必要的比较次数。