在Python中查找等差数列中被移除的项的程序
假设我们有一个名为nums的数组,它包含n-1个等差数列项。除第一个或最后一个元素外,还删除了一个元素。我们必须找到被删除的数字。
因此,如果输入是nums = [5,7,11,13],则输出将为9,因为项目遵循公式2i + 5,因此对于i = 2,它将是2 * 2 + 5 = 9,它被删除了。
要解决此问题,我们将执行以下步骤:
- 如果nums的大小与2相同,则:
- 返回nums中所有元素的总和的floor值
- 如果nums [0]与nums [1]相同,则:
- 返回nums [0]
- lower := nums [0]
- upper := nums的最后一个元素
- interval :=(upper-lower)/ nums的大小的floor值
- pointer := nums的大小/ 2的floor值
- left := 0
- right := nums的大小-1
- while 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的floor值
- 否则,执行以下操作:
- 如果right-left等于1,则:
- pointer := right
- 否则,执行以下操作:
- left := pointer
- pointer :=(left + right)/ 2的floor值
- 如果nums [pointer]不同于nums [0] + interval * pointer,则
示例
让我们看下面的实现以获得更好的理解
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