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 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習