难度: Easy
Submission
运行时间: 24 ms
内存: 16.9 MB
class Solution:
def fixedPoint(self, arr: List[int]) -> int:
# for index, val in enumerate(arr):
# if index == val:
# return index
# return -1
l = 0
r = len(arr) - 1
res = -1
while l <= r:
m = (l + r) // 2
if m < arr[m]:
r = m - 1
elif m > arr[m]:
l = m + 1
else:
res = m
r = m - 1
return res
Explain
这个题解使用了二分查找的方法来寻找数组中的不动点（即索引和值相等的位置）。算法从数组的两端开始，计算中点，然后比较中点的索引和值。如果中点的值大于索引，则不动点必定在左侧；如果中点的值小于索引，则不动点必定在右侧；如果中点的值等于索引，该中点可能是一个不动点，但还需要继续向左搜索以寻找可能存在的更小的不动点索引。这种方法能够有效地缩小搜索范围，从而快速找到最左侧的不动点或确定不存在不动点。
时间复杂度: O(log n)
空间复杂度: O(1)
class Solution:
def fixedPoint(self, arr: List[int]) -> int:
l = 0 # 初始化左指针
r = len(arr) - 1 # 初始化右指针
res = -1 # 存储结果，初始值为-1，表示未找到不动点
while l <= r: # 当左指针不超过右指针时进行循环
m = (l + r) // 2 # 计算中点
if m < arr[m]: # 如果中点的值大于中点索引
r = m - 1 # 移动右指针到中点左侧
elif m > arr[m]: # 如果中点的值小于中点索引
l = m + 1 # 移动左指针到中点右侧
else: # 如果中点的值等于中点索引
res = m # 更新结果为当前中点
r = m - 1 # 继续向左搜索可能的更小的不动点
return res # 返回结果
Explore
在找到一个不动点后，继续向左搜索是为了找到可能存在的更小的不动点索引。数组中可能存在多个不动点，即多个索引 i 满足 arr[i] = i。因此，为了确保找到最左侧的不动点（即最小索引的不动点），算法在找到一个不动点后还需要继续检查左侧区间。
为了确保找到最左侧的不动点，算法在发现中点 m 等于 arr[m] 时，会更新结果变量 res 为 m，但不会立即结束循环。而是将右指针 r 移动到 m - 1，继续在左侧区间进行搜索。这样可以保证如果存在更小的不动点索引，算法会更新 res 为那个更小的索引。继续搜索直到左指针大于右指针，确保覆盖所有可能的情况。
如果数组中没有不动点，这种二分查找方法仍然会及时终止，并不会遍历整个数组。在每一步中，算法都会根据中点的值与索引的比较结果调整搜索范围，并逐步缩小这个范围。当左指针大于右指针时，循环结束，这通常发生在搜索区间被完全排除之后。因此，即使没有不动点，二分查找也只会检查对数数量的元素，而不是整个数组。
在中点的值等于中点索引时，尽管当前中点是一个不动点，但我们需要确保它是最左侧的不动点。因此，将右指针移动到中点的左侧继续搜索可以帮助我们探索是否存在一个索引更小的不动点。这样做是为了找到所有可能的不动点中最左侧的一个，这个步骤是必要的以保证算法的正确性和完整性。