C语言编程实现: 给你一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现 两次。 找出只出现一次的那两个元素。你可以按任意顺序返回答案。
时间: 2024-01-30 19:55:12 浏览: 29
解题思路:
利用异或运算的性质,对所有元素进行异或操作,得到的结果就是两个只出现一次的元素的异或结果。因为其他元素都是出现两次,所以它们的异或结果为0。
然后我们找到异或结果中第一个为1的位,这个位说明这两个只出现一次的元素在这一位上不同。我们可以根据这一位将原数组分成两个子数组,每个子数组内部的元素都出现两次,而只有一个子数组包含一个只出现一次的元素,另一个子数组不包含。
然后我们再对这两个子数组分别进行异或操作,得到的结果就是两个只出现一次的元素。
具体实现:
1.对所有元素进行异或操作,得到两个只出现一次的元素的异或结果。
2.找到异或结果中第一个为1的位,即两个只出现一次的元素在这一位上不同。
3.根据这一位将原数组分成两个子数组。
4.分别对两个子数组进行异或操作,得到两个只出现一次的元素。
C语言代码实现如下:
相关问题
给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素
这道题可以使用异或运算来解决,具体步骤如下:
1. 首先对整个数组进行一次异或运算,得到的结果就是两个只出现一次的元素的异或结果。
2. 因为这两个元素不相同,所以它们的二进制表示中至少有一位是不同的。我们可以根据这一位将所有元素分成两组,一组该位是 0,一组该位是 1。然后分别对这两组进行异或运算,得到的结果就是两个只出现一次的元素。
下面是代码实现:
```python
def findSingleNums(nums):
# 对整个数组进行异或运算
xor = 0
for num in nums:
xor ^= num
# 找到两个只出现一次的元素在二进制下不同的那一位
mask = 1
while (mask & xor) == 0:
mask <<= 1
# 根据这一位将所有元素分成两组
a, b = 0, 0
for num in nums:
if num & mask:
a ^= num
else:
b ^= num
return a, b
```
时间复杂度为 O(n),空间复杂度为 O(1)。
给你一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次或两次以上。 找出只出现一次的那两个元素。你可以按任意顺序返回答案。
题目描述:给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次或两次以上。 找出只出现一次的那两个元素。你可以按任意顺序返回答案。
解题思路:使用异或运算,将所有元素异或起来,得到的结果就是两个只出现一次的元素异或的结果。因为这两个元素不相同,所以异或结果中至少有一位是1,找到这个1所在的位置,然后将数组中所有元素按照这个位置是否为1分成两组,这样两个只出现一次的元素就被分到了不同的组中,然后对每组中的元素分别异或,得到的结果就是这两个只出现一次的元素。
参考代码:
```python
class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
xor = 0
for num in nums:
xor ^= num
mask = 1
while xor & mask == 0:
mask <<= 1
a, b = 0, 0
for num in nums:
if num & mask == 0:
a ^= num
else:
b ^= num
return [a, b]
```