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

示例

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

Open Compiler
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]

Learn Python in-depth with real-world projects through our Python certification course. Enroll and become a certified expert to boost your career.

输出

9

更新于:2021年10月11日

155 次浏览

开启您的职业生涯

完成课程获得认证

开始学习
广告