数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究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 次浏览
广告