Given an integer array nums
where every element appears three times except for one, which appears exactly once. Find the single element and return it.
You must implement a solution with a linear runtime complexity and use only constant extra space.
Example 1:
Input: nums = [2,2,3,2] Output: 3
Example 2:
Input: nums = [0,1,0,1,0,1,99] Output: 99
Constraints:
1 <= nums.length <= 3 * 104
-231 <= nums[i] <= 231 - 1
- Each element in
nums
appears exactly three times except for one element which appears once.
Solution: Bit by bit
Since every number appears three times, the i-th bit must be a factor of 3, if not, that bit belongs to the single number.
Time complexity: O(32n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// Author: Huahua class Solution { public: int singleNumber(vector<int>& nums) { int ans = 0; for (int s = 0; s < 32; ++s) { int mask = 1 << s; int sum = 0; for (int x : nums) if (x & mask) ++sum; if (sum % 3) ans |= mask; } return ans; } }; |
Related Problems
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment