利用 Python 从元素列表中查找重复项的程序

假设我们有一个名为 nums 的元素列表，大小为 n + 1，它们选自范围 1、2、...、n。众所周知，根据鸽巢原理，一定会有重复元素。我们必须找到重复元素。我们的目标是在 O(n) 时间和常数空间内完成此任务。

因此，如果输入类似 nums = [2,1,4,3,5,4]，那么输出将是 4

为了解决这个问题，我们将按照以下步骤进行操作 −

  • q := nums 中所有元素的和

  • n := nums 的大小

  • v := ((n - 1)*(n)/2) 的下限

  • return q - v

示例

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

def solve(nums):
   q = sum(nums)
   n = len(nums)
   v = (n - 1) * (n) // 2
   return q - v

nums = [2,1,4,3,5,4]
print(solve(nums))

输入

[2,1,4,3,5,4]

输出

4

更新于： 2021-10-11

153 人查看

开启您的职业生涯

通过完成课程获得认证

开始学习
广告