Python程序：查找数组中元素值等于其索引的最小索引

假设我们有一个名为 nums 的元素列表，其中所有项目都是唯一的，并且按升序排序，我们需要找到最小的 i，使得 nums[i] = i。如果我们找不到任何解决方案，则返回 -1。我们需要在 O(log(n)) 时间内解决此问题。

因此，如果输入类似于 nums = [-4, -1, 2, 3, 8]，则输出将为 2，因为 nums[2] = 2 和 nums[3] = 3，但 2 更小。

为了解决这个问题，我们将遵循以下步骤：

• ret := -1, lhs := 0, rhs := nums 的大小 - 1

• 当 lhs <= rhs 时，执行以下操作：

  • mid := (lhs + rhs) / 2 的向下取整

  • 如果 nums[mid] 等于 mid，则：

    • ret := mid

  • 如果 nums[mid] >= mid，则：

    • rhs := mid - 1

  • 否则：

    • lhs := mid + 1

• 返回 ret

示例

让我们查看以下实现以更好地理解

def solve(nums):
   ret = -1
   lhs = 0
   rhs = len(nums) - 1
   while lhs <= rhs:
      mid = (lhs + rhs) // 2
      if nums[mid] == mid:
         ret = mid
      if nums[mid] >= mid:
         rhs = mid - 1
      else:
         lhs = mid + 1
   return ret

nums = [-4, -1, 2, 3, 8]
print(solve(nums))

输入

[-4, -1, 2, 3, 8]

输出

2

Arnab Chakraborty

更新于: 2021年10月11日

111 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习