Python程序：查找等差数列中移除的项

假设我们有一个名为nums的数组，其中包含n-1个等差数列项。在移除一个元素（除了第一个或最后一个元素）之前。我们需要找到被移除的数字。

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

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

  • 如果nums的大小为2，则

    • 返回nums中所有元素之和的向下取整/2

  • 如果nums[0]等于nums[1]，则

    • 返回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 :=向下取整(left + right) / 2

    • 否则，

      • 如果right - left等于1，则

        • pointer := right

      • 否则，

        • left := pointer

        • pointer := 向下取整(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))

输入

[5, 7, 11, 13]

输出

9

更新于：2021年10月11日

155 次浏览

开启您的职业生涯

完成课程获得认证

开始学习
广告