Description
Given an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in any order.
You must write an algorithm that runs in linear runtime complexity and uses only constant extra space.
Example 1:
Input: nums = [1,2,1,3,2,5]
Output: [3,5]
Explanation: [5, 3] is also a valid answer.
Example 2:
Input: nums = [-1,0]
Output: [-1,0]
Example 3:
Input: nums = [0,1]
Output: [1,0]
Constraints:
2 <= nums.length <= 3 * 104
-231 <= nums[i] <= 231 - 1
Each integer in nums will appear twice, only two integers will appear once.
Solution
Sort
Use sort to get the sorted list, then use the pointer to iterate the whole list. When we see the element next to current element is identical, we move pointer 2 steps forward, otherwise we append the current element to list and move the pointer 1 step forward.
Time complexity:
o
(
n
log
n
)
o(n \log n)
o(nlogn)
Space complexity:
o
(
1
)
o(1)
o(1)
Bit Manipulation
By xor all the element, we could get a ^ b, and it must contains 1 because a and b are two different numbers. We randomly select one digit that is 1 in a ^ b, then a and b are in different groups. One group has 1 in this digit while the other group has 0. We start over again to iterate the list, and all the other elements must be divided into these two groups. a will be the only single element in its group, and so does b. Then by xor we could get these two numbers.文章来源：https://www.toymoban.com/news/detail-503368.html
Time complexity:
o
(
n
)
o(n)
o(n)
Space complexity:
o
(
1
)
o(1)
o(1)文章来源地址https://www.toymoban.com/news/detail-503368.html
Code
Sort
class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
if len(nums) == 2:
return nums
nums.sort()
res = []
p = 0
while p < len(nums):
if p + 1 < len(nums) and nums[p] == nums[p + 1]:
p += 2
else:
res.append(nums[p])
p += 1
return res
Bit Manipulation
class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
a_xor_b = 0
for each_num in nums:
a_xor_b ^= each_num
digit = a_xor_b & (-a_xor_b)
a_group, b_group = 0, 0
for each_num in nums:
if each_num & digit == 0:
a_group ^= each_num
else:
b_group ^= each_num
return [a_group, b_group]
到了这里，关于leetcode - 260. Single Number III的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
