Python程式：查詢插入元素以保持列表排序的索引

假設我們有一個名為 nums 的數字列表，它們按升序排序，我們還有一個數字 target，我們需要找到應該插入 target 以保持 nums 排序的索引。如果 target 已經存在於 nums 中，則返回可以插入 target 的最大索引。我們需要在不使用庫函式的情況下解決這個問題，並在 O(log n) 時間內解決。

因此，如果輸入類似於 nums = [1,5,6,6,8,9] target = 6，則輸出將為 4，因為 6 已經存在，所以要插入它，最大的可能索引是 4，所以陣列將類似於 [1,5,6,6,6,8,9]。

要解決此問題，我們將遵循以下步驟：

• left := 0
• right :=
• nums 的大小 - 1
• ans := 0
• 當 left <= right 時，執行以下操作：
  • mid := (left + right) / 2 的向下取整
  • 如果 target >= nums[mid]，則：
    • ans := mid + 1
    • left := mid + 1
  • 否則：
    • right := mid - 1
• 返回 ans

示例

讓我們看看下面的實現，以便更好地理解：

def solve(nums, target):
   left, right = 0, len(nums) - 1
   ans = 0
   while left <= right:
      mid = (left + right) // 2
      if target >= nums[mid]:
         ans = mid + 1
         left = mid + 1
      else:
         right = mid - 1
   return ans

nums = [1,5,6,6,8,9]
target = 6
print(solve(nums, target))

輸入

[1,5,6,6,8,9], 6

輸出

4

Arnab Chakraborty

更新於: 2021年10月18日

592 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習