Question
Formatted question description: https://leetcode.ca/all/137.html
137 Single Number II
Given an array of integers, every element appears three times except for one. Find that single one.
Example 1:
Input: [2,2,3,2]
Output: 3
Example 2:
Input: [0,1,0,1,0,1,99]
Output: 99
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
@tag-bit
Algorithm
A 32-bit number can be created to count the number of occurrences of 1 in each digit.
If a certain digit is 1, then if the integer appears three times, the remainder of 3 is 0, so that the numbers of each digit position are added up then take the remainder of 3, and the final number remaining is a single number.
Code
Java
-
public class Single_Number_II { public class Solution { public int singleNumber(int[] nums) { if (nums == null || nums.length == 0) { return 0; } // first doubt, how long bits should I check. // int is 32 bit, so bitmap length is 32 int single = 0; for (int bitPos = 0; bitPos < 32; bitPos++) { int sumAtThisPos = 0; for (int j = 0; j < nums.length; j++) { int digitInA = ((nums[j] >> bitPos) & 1); sumAtThisPos += digitInA; } int afterMod = sumAtThisPos % 3; single |= (afterMod << bitPos); } return single; } } }
-
// OJ: https://leetcode.com/problems/single-number-ii/ // Time: O(N) // Space: O(1) class Solution { public: int singleNumber(vector<int>& nums) { unsigned ans = 0; for (int i = 0; i < 32; ++i) { int cnt = 0; for (unsigned n : nums) { cnt = (cnt + ((n >> i) & 1)) % 3; } ans |= cnt << i; } return ans; } };
-
class Solution(object): def singleNumber(self, nums): """ :type nums: List[int] :rtype: int """ def singleNumberK(nums, k): ret = 0 count = [0] * 32 for i in range(0, 32): for num in nums: if num & (1 << i): count[i] += 1 if count[i] % 3 != 0: ret |= 1 << i if ret > 0x7fffffff: ret -= 0x100000000 return ret return singleNumberK(nums, 3)