查找出现一次的数字

2024年8月29日 | 阅读 7 分钟

假设有一个数组，其中所有元素都出现了三次，只有一个元素只出现一次。找出那个只出现一次的元素。我们应该以 O(n) 的时间复杂度和 O(1) 的额外空间来解决这个问题。

示例

输入: arr[] = {2, 5, 6, 6, 5, 1, 3, 3, 5, 1, 1, 5}

输出 2

除了 2 出现一次外，输入数组中的每个元素都出现了三次。

输入: arr[] = {10, 19, 21, 20, 21, 10, 19, 19, 10}

输出 20

除了 20 出现一次外，输入数组中的每个元素都出现了多次。

排序允许我们在 O(n Logn) 的时间内完成任务。我们也可以使用哈希，它需要更多的空间，但最坏情况下的时间复杂度是 O(n)。

方法 - 1

目标是利用位运算符提供一个 O(n) 时间和 O(1) 额外空间的解决方案。由于所有元素的出现次数都是奇数，因此解决方案不像以前基于 XOR 的方法那样直接。

对于数组中的每个元素，执行一个循环。在每次迭代结束时保持以下两个值不变。

One: 出现一次、四次、七次等的元素。
Two: 出现二次、五次、八次等的元素。

然后我们返回“one”的值。

如何维护 'one' 和 'two' 的值？

我们将两个变量 'one' 和 'two' 初始化为 0。在每次迭代中，我们将找到当前元素和 'one' 前一个值之间的共同位。我们将这些共同位添加到变量 'two' 中。对于这个操作，我们将使用 XOR。Two 中会包含一些额外的位，我们稍后会移除它们。

通过将当前元素与 'one' 的前一个值进行 XOR 来更新 'one'。一些位可能出现三次。我们稍后会移除这些额外的位。

代码

# Python3 program to find to element with a single occurrence using a bitwise operator

# Defining a function that will take the array and the length of the array and return the element with a single occurrence
def getSingleoccurence(array, n):
   one = 0
   two = 0
   
   for i in range(n):
     # 'one & array[i]' results in the bits that are present in both 'one' and the new element from array[]. By utilizing bitwise XOR, we will add these bits to the "two."
     two = two ^ (one & array[i])
     
     # array[i] provides the bits that are present in both 'one' and the new element from array[]. By utilizing bitwise XOR, we will add these bits to the "one."
     one = one ^ array[i]
     
     # The third-appearing components are the most prevalent. This means that these bits shouldn't be present in both "one" and "two." To enable the removal of the bits from "one" and "two," common_bit has all of these bits as 0.
     common_bit = ~(one & two)
     
     # Removing the common bits from 'one.'
     # These are the bits appearing for the third time) from
     one &= common_bit
     
     # Removing the common bits from 'two.'
     # These are the bits appearing for the third time) from
     two &= common_bit
   return one
   
# Creating an array and passing it to the function
array = [2, 5, 6, 6, 5, 1, 3, 3, 5, 1, 1, 5]
n = len(array)
print("The element that occurs only once is ", getSingleoccurence(array, n))

输出

The element that occurs only once is 2

时间复杂度: 此方法的最佳时间复杂度为 O(n)，其中 n 是数组中的元素数量。

辅助空间: 由于我们只创建了常量，因此此方法使用 O(1) 的额外内存空间。

方法 - 2

这是另一种方法，时间复杂度为 O(n)，额外空间为 O(1)。对于所有整数，我们可以将相同位置的位相加，然后取该和与 3 的模。总和不是 3 的倍数的位是只出现一次的数字的位。

例如，我们将考虑数组 [6, 6, 6, 8]。它们是 110, 110, 110, 1000

(第一位之和) % 3 = (0 + 0 + 0 + 0) % 3 = 0;

(第二位之和) % 3 = (1 + 1 + 1 + 0) % 3 = 0;

(第三位之和) % 3 = (1 + 1 + 1 + 0) % 3 = 0;

(第四位之和) % 3 = (1) % 3 = 1;

因此，只出现一次的数字是 1000（二进制），即 8。

注意：此算法不适用于负数。

这是该算法的实现。

代码

# Python3 program to find the element with a single occurrence

# Initializing the maximum bit size of the integer
int_ = 32

def getSingleoccurence(array, n) :
   
   # Initializing the result
   res = 0
   
   # Iterating through every bit of the integer
   for i in range(0, int_) :
     
     # Finding the sum of the set of bits present at the ith position in all the array elements
     summ = 0
     s = (1 << i)
     for _ in range(0, n):
       if (array[_] & s):
         summ = summ + 1
         
     # The bits of a number with a single occurrence are those whose sum is not a multiple of 3.
     if (summ % 3)!= 0 :
       res = res | s
   
   return res
   
# Creating an array and passing it to the function
array = [2, 5, 6, 6, 5, 1, 3, 3, 5, 1, 1, 5]
n = len(array)
print("The element that occurs only once is ", getSingleoccurence(array, n))

输出

The element that occurs only once is 2

时间复杂度: 此方法的最佳时间复杂度为 O(n)，其中 n 是数组中的元素数量。

辅助空间: 由于我们只创建了常量，因此此方法使用 O(1) 的额外内存空间。

方法 - 3

在第三种方法中，我们将使用以下公式：

( 3 * (不重复数组元素之和) - (所有数组元素之和) ) / 2

设数组为 arr[] = [2, 5, 6, 6, 5, 1, 3, 3, 5, 1, 1, 5, 3, 1]

summ = (3 * (不重复数组元素之和) - (所有数组元素之和)) / 2

= (3 * (2 + 5 + 6 + 1 + 3) - (2 + 5 + 6 + 6 + 5 + 1 + 3 + 3 + 5 + 1 + 1 + 5 + 3 + 1)) / 2

= (3 * 17 - 47) / 2

= (51 - 47) / 2

= 2 （这是所需答案）

我们知道集合数据结构不包含重复元素。我们将使用此数据结构来查找数组不重复元素的总和。但是，在此数据结构上的插入过程的最坏成本为 O(log(n))。在这里，我们将使用 Python 集合。

这是该算法的实现。

代码

# Python3 program to find the element of a single occurrence using the formula given above

# Defining the function which will take the array as its parameter
def getSingleoccurence(array):
   
   # using the formula given above.
   return int((3 * sum(set(array)) - sum(array)) / 2)

# Creating an array and passing it to the function
array = [2, 5, 6, 6, 5, 1, 3, 3, 5, 1, 1, 5, 3, 1]
n = len(array)
print("The element that occurs only once is ", getSingleoccurence(array))

输出

The element that occurs only once is 2

时间复杂度: O(N log(N))

辅助空间：O(N)

方法 - 4

最后一种方法是使用 Counter 函数。

使用 Counter 是最直接的方法。以下是该方法中的算法。

我们将使用 Counter 函数查找数组中每个元素的频率。

我们将遍历 Counter 字典，并使用 if 条件检查当前键的值是否等于 1。

如果键的值为 1，则返回该键。

这是该方法中的实现。

代码

# Python program to find the element of a single occurrence

# Importing the required class
from collections import Counter

# Defining a function that will take an array as input and return the element of a single occurrence
def getSingleOcurence(array):
  
   # Finding the frequencies of each element using the Counter class
   frequency = Counter(array)
   
   # traversing through the Counter frequency dictionary 
   for i in frequency:
     # checking if the key has value = 1
     if(frequency[i] == 1):
       return i

# Creating an array and passing it to the function
array = [2, 5, 6, 6, 5, 1, 3, 3, 5, 1, 1, 5, 3, 1]
n = len(array)
print("The element that occurs only once is ", getSingleOcurence(array))

输出

The element that occurs only once is 2

时间复杂度：O(N)

辅助空间： O(1)

方法 #5：使用 count() 方法。

我们可以使用 count() 方法查找元素的出现次数。如果 count() 方法返回 1，则该元素出现一次。

C++
Java
Python3
C#
Javascript

# Python3 code to find the element that
# appears once
 
arr = [3, 3, 2, 3]
for i in arr:
    if(arr.count(i)==1):
        x=i
        break
print("The element with single occurrence is ",x)

输出

The element with single occurrence is  2

时间复杂度：O(n^2)

辅助空间： O(1)

下一话题使用 Python 分析客户行为

← 上一个下一个 →

查找出现一次的数字

示例

方法 - 1

如何维护 'one' 和 'two' 的值？

方法 - 2

注意：此算法不适用于负数。

方法 - 3

方法 - 4

方法 #5：使用 count() 方法。

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Python 问题

查找出现一次的数字

示例

方法 - 1

如何维护 'one' 和 'two' 的值？

方法 - 2

注意：此算法不适用于负数。

方法 - 3

方法 - 4

方法 #5：使用 count() 方法。

相关帖子

Python 中的物理计算

编写 Python 代码展平链表

如何在 Python 中解包字典

Python 列表推导式

Python 项目 - 使用深度学习进行乳腺癌分类

Python 中的最小堆实现

边缘计算项目创意列表 第二部分

Python Secret 模块

Python 中的 GUI 计算器

Python 中的 Enum 类

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器

边缘计算项目创意列表第二部分