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

更新于: 2021年10月18日

592 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告