编写 Python 程序查找给定列表中的缺失元素

在本教程中，我们将编写程序来查找给定列表中 1 到 N 范围内的缺失元素。

问题陈述

问题陈述是给定一个大小为 N-1 的数组，其中只包含 1 到 N 范围内的不重复整数。找出缺失的元素。

示例 - 1

输入

N = 5

A = [1,2,3,5]

输出

4

示例 - 2

输入

N = 10

A = [6,1,2,8,3,4,7,10,5]

输出

9

解决方案

我们可以用两种方法解决这个问题。让我们看第一种方法。

方法 - 1：整数之和

我们可以按照以下步骤操作 -

1. 使用公式计算 1 到 N 的整数之和：sum = N*(N+1)/2
2. 遍历数组并计算数组中所有元素的总和。
3. 将步骤 2 中获得的数组之和减去步骤 1 中获得的整数之和。
4. 我们将得到缺失的元素。

让我们看以下代码。

示例 -

输出

The missing element is: 4

解释 -

上面的代码，我们创建了 find_missing_element() 函数，它将列表的长度和整数列表作为参数。我们使用公式计算 1 到 N 的整数之和，然后将数组元素相加，通过将数组之和与整数之和相减来找到缺失的元素。此解决方案的时间复杂度为 O(N)，因为它需要遍历整个数组。

方法 - 2：二分查找

我们将使用二分查找算法解决这个问题。下面是步骤。

1. 首先，我们将给定数组按升序排序。
2. 初始化两个指针，left 和 right，分别指向数组的第一个和最后一个索引。
3. 当 left <= right 时，执行以下操作
4. 将中间索引 mid 计算为 (left + right) // 2。
5. 如果 mid 的值等于 mid + 1，则缺失的元素位于数组的右半部分。将 left 指针移动到 mid + 1。
6. 否则，缺失的元素位于数组的左半部分。将 right 指针移动到 mid - 1。
7. 在循环结束时，left（或 right，它们是相同的）处的值将是缺失的元素。

让我们看下面的 Python 代码。

示例 -

输出

The missing element is: 9

解释 -

优化后的解决方案使用二分查找更有效地找到缺失的元素。

我们首先将数组按升序排序，然后初始化两个指针，left 和 right，分别指向数组的第一个和最后一个索引。

然后我们计算中间索引，并确定缺失的元素是在数组的左半部分还是右半部分。

我们重复这个过程，直到找到缺失的元素，该元素将位于 left 指向的索引处。此解决方案的时间复杂度为 O(log N)，因为我们在每次迭代中消除了数组的一半。