用 Python 编写程序从等差序列中查找已删除项

pythonserver side programmingprogramming更新于 2025/12/17 16:12:17

假设我们有一个名为 nums 的数组，其中包含 n-1 个等差序列项。除了 nums 的第一个或最后一个元素之外，还有一个元素之前已被删除。我们必须找到被移除的数字。

因此，如果输入为 nums = [5, 7, 11, 13]，则输出将为 9，因为项目遵循公式 2i+5，因此对于 i = 2，它将是 2*2 + 5 = 9，这是缺失的。

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

如果 nums 的大小与 2 相同，则
- 返回 (nums 中存在的所有元素的总和)/2 的下限
如果 nums[0] 与 nums[1] 相同，则/p>
- 返回nums[0]
lower := nums[0]
upper := nums 的最后一个元素
interval := (upper - lower) 的下限 / nums 的大小
pointer := nums 的大小 / 2 的下限
left := 0
right := nums 的大小 - 1
如果 left 与 right 不同，则执行
- 如果 nums[pointer] 与 nums[0] + interval * pointer 不同，则
  - 如果 nums[pointer - 1] 与nums[0] + interval *(pointer - 1) ，然后
    - 返回 nums[0] + interval * pointer
  - 否则，
    - right := pointer
    - pointer :=floor of(left + right) / 2
- 否则，
  - 如果 right - left 与 1 相同，则
    - pointer := right
  - 否则，
    - left := pointer
    - pointer := floor of(left + right) / 2

示例

让我们看看下面的实现以便更好地理解

def solve(nums):
   if len(nums) == 2:
      return sum(nums) // 2

   if nums[0] == nums[1]:
      return nums[0]

   lower = nums[0]
   upper = nums[-1]
   interval = (upper - lower) // len(nums)

   pointer = len(nums) // 2

   left = 0
   right = len(nums) - 1

   while left != right:
      if nums[pointer] != nums[0] + interval * pointer:
         if nums[pointer - 1] == nums[0] + interval * (pointer -1):
            return nums[0] + interval * pointer
         else:
            right = pointer
            pointer = (left + right) // 2
      else:
         if right - left == 1:
            pointer = right
         else:
            left = pointer
            pointer = (left + right) // 2

nums = [5, 7, 11, 13]
print(solve(nums))