大家好!因此,在本教程中,我们将了解这个简单的问题,即在数字列表中查找丢失和重复的元素。让我们通过一个例子来理解这个问题,考虑下面给出的 n = 6 的数字列表。
1 | 2 | 4 | 5 | 5 | 6 |
缺失的数字是数字 1、2、3… 中不存在的数字。n 和重复数字将是元素中出现两次的数字。
在上述情况下,缺失的数字将为 3,重复的数字将为 5。实际结果必须如下所示:1 2 3 4 5 6 才能没有重复和缺失的数字。
另请阅读:Python 列表与数组
手动查找丢失和重复的元素
现在,手动方法是遍历列表一次并检查每个数字的计数。
如果任何数字的计数等于 2*n,那么我们找到重复的数字,然后遍历元素以检查每个数字的出现情况:一、二、三等。
如果其中任何数字不存在,则返回该数字作为缺失的数字。
这种方法的问题是这种方法很慢,对于一个简单的问题引入了太多步骤,并且可以用更好的方式来完成。
查找缺失和重复元素的更好方法
因此,我们将创建一个额外的数组,该数组将考虑元素是否被访问。数组的大小与n的值相同。
最初,所有值都等于 0(未见),当某个元素在数组中出现时,其在最终数组中的值将设置为 1(已见)。
这一直持续到数组末尾。我们必须计算两件事:重复数和缺失数。
如果在任何时候,正在设置其值的数字已经被设置,则这意味着该数字是重复数字。
现在为了计算缺失的数字,我们将最后一次遍历最终数组并检查最终数组中哪个数字的值仍然为 0。这意味着该数字从未见过,因此它是数组中缺失的数字。
我们将以具有两个值的列表的形式返回两个值:第一个是重复的数字,第二个是缺失的数字。
用Python实现
我希望你清楚这一点。现在让我们看看查找缺失和重复元素的代码实现以及代码的示例输出。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
def find_miss_repeat(arr,n): final_array = [ 0 for i in range (n)] l = [ 0 , 0 ] for i in arr: if (final_array[i - 1 ] = = 1 ): l[ 0 ] = i else : final_array[i - 1 ] = 1 for i in range ( len (final_array)): if (final_array[i] = = 0 ): l[ 1 ] = i + 1 return l x = find_miss_repeat([ 1 , 2 , 4 , 5 , 5 , 6 ], 6 ) print ( "Repeating Number: " ,x[ 0 ]) print ( "Missing Number: " ,x[ 1 ]) |
代码的输出如下所示。
Repeating Number: 5 Missing Number: 3 |
结论
我希望您清楚这个概念。您可以使用简单方法和快速方法自行尝试。相同的逻辑也适用于所有编程语言。
感谢您阅读本教程!快乐编码!😇