难度: Medium
Submission
运行时间: 66 ms
内存: 26.5 MB
class Solution:
def binarySearchableNumbers(self, nums: List[int]) -> int:
n = len(nums)
ok = [1] * n
mx, mi = -1000000, 1000000
for i, x in enumerate(nums):
if x < mx:
ok[i] = 0
else:
mx = x
for i in range(n - 1, -1, -1):
if nums[i] > mi:
ok[i] = 0
else:
mi = nums[i]
return sum(ok)
Explain
该题解的核心思路是检查每个数组元素是否可以通过二分搜索确定其位置。一个元素x是可被二分搜索的，如果它的位置不受其左侧元素的最大值和右侧元素的最小值的影响。算法首先从左向右遍历数组，记录到目前为止的最大值，如果当前元素小于这个最大值，则其不可能是可被二分搜索的元素。接着，算法从右向左遍历数组，记录到目前为止的最小值，如果当前元素大于这个最小值，则其同样不可能是可被二分搜索的元素。最终，所有同时不被左侧最大值和右侧最小值影响的元素计数即为答案。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def binarySearchableNumbers(self, nums: List[int]) -> int:
n = len(nums) # 数组长度
ok = [1] * n # 初始化所有元素均可被二分搜索
mx, mi = -1000000, 1000000 # 初始化最大值和最小值
for i, x in enumerate(nums): # 从左向右遍历
if x < mx: # 如果当前元素小于到目前为止的最大值
ok[i] = 0 # 标记为不可被二分搜索
else: # 否则更新最大值
mx = x
for i in range(n - 1, -1, -1): # 从右向左遍历
if nums[i] > mi: # 如果当前元素大于到目前为止的最小值
ok[i] = 0 # 标记为不可被二分搜索
else: # 否则更新最小值
mi = nums[i]
return sum(ok) # 返回可被二分搜索的元素数量
Explore
在算法中从两个方向遍历数组是为了确保每个元素在其位置上是否独立于其左侧和右侧的元素。对于一个元素来说，只有当它大于其左侧所有元素的最大值并且小于其右侧所有元素的最小值时，才能通过二分搜索准确地被定位。因此，从左向右遍历来更新最大值，确保元素大于其左侧的所有元素；从右向左遍历来更新最小值，确保元素小于其右侧的所有元素。这两个条件同时满足时，该元素才是可被二分搜索的。
将最大值初始化为-1000000可能不是安全的选择，因为这个值可能不适用于所有范围的数据。例如，如果数组中包含比-1000000还小的值，那么这个初始化就会导致错误的结果。更安全的做法是使用数组中的第一个元素作为初始化的最大值，这样可以确保处理的逻辑始终适用于任何数据类型和范围。
如果数组中存在重复元素，该算法会标记所有重复元素中第一个出现的为可搜索（如果它大于之前所有元素的最大值），而之后出现的重复元素都会被标记为不可搜索（因为它们不小于前面的元素，即不满足小于右侧所有元素的最小值的条件）。这意味着除非重复元素是连续的一段中的第一个，并且没有其他左侧元素大于它，否则这些重复元素不会被认为是可二分搜索的。
要修改算法以返回可被二分搜索的元素的索引，可以在遍历过程中保存满足条件的元素的索引而非计数。具体来说，可以初始化一个空列表用来存储索引，然后在最后的遍历中，如果元素满足可被二分搜索的条件（即ok数组中对应位置为1），则将该索引添加到列表中。最后返回这个列表即可。