How does LeetCode find numbers that appear only once
This article mainly shows you "how LeetCode finds out numbers that appear only once". The content is simple and easy to understand, and the organization is clear. I hope it can help you solve your doubts. Let Xiaobian lead you to study and learn this article "how LeetCode finds out numbers that appear only once".
1
Title Description
Given an array of non-empty integers where only one number appears once and the rest three times, find the number that appears only once. For example, input [3, 4, 5, 4, 3, 3], output 5.
2
problem-solving
Idea 1: Set Difference
Slice the set to generate three sets and find the missing numbers for the sets that differ from the other two sets. For example, the set [2, 2, 3, 2] is sorted first to obtain [2, 2, 2, 3], and the sets [2, 3],[2], and [2] are generated by slicing, and the element differences between the sets are compared to obtain the output result 3.
class Solution: def singleNumber(self, nums: List[int]) -> int: nums.sort() a=len(set(nums[::2])) b=len(set(nums[1::2])) if a==b: return list(set(nums[::3]) - set(nums[2::3]))[0] else: return list(set(numbers [::3]) - set(numbers [1::3]))[0] Idea 2: Bit operation
By using the set method, the space-time complexity is O(N), and the bit operation can reduce the space complexity to O(1). In LeetCode brush problem DAY 5: only appear once in the number of "exclusive OR" in fact is the same state appears twice will return to zero, that is, 0->1->10=0 change, in this question is to let the same state appear three times to zero, that is, 00->01->10->11=00, it can be seen here need to use two bits for state recording.
It is important to note here that two and one are calculated separately. For one, when two=1, the next one is 0 regardless of the input, when two=0, input 1 is one=~one, input 0 is one unchanged. For two, depending on the state of one after change, when one new state is 1, two is 0, when one new state is 0, input 1 two=~two, input 0 is unchanged. Because three occurrences return to zero, one ends up with a value that only occurs once.
class Solution: def singleNumber(self, nums: List[int]) -> int: one,two = 0,0 for i in nums: one = one^i & ~two two = two^i & ~one return one Of course, traversing the set, recording the number of occurrences of each number through the hash table is also possible, and the space-time complexity is also O(N). The code is consistent with the idea of Day 5, so I won't repeat it here. That's all for "How LeetCode finds numbers that only appear once." Thanks for reading! I believe that everyone has a certain understanding, hope to share the content to help everyone, if you still want to learn more knowledge, welcome to pay attention to the industry information channel!
