137. Single Number II

Medium (Trung bình) C++ Python 🔗 Xem trên LeetCode

📋 Đề Bài

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.

🧠 Thuật Toán & Kỹ Thuật

Bit Manipulation (Thao tác bit)
⏱️ Thời gian O(n²)
💾 Không gian O(n)

💻 Lời Giải

C++ 0137-single-number-ii.cpp 
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for (int i = 31; i >= 0; --i) {
            int cntBit1 = 0;
            for (int num : nums) {
                if ((num >> i) & 1) {
                    cntBit1++;
                }
            }
            cntBit1 %= 3;
            if (cntBit1) {
                ans |= 1 << i;
            }
        }
        return ans;
    }
};
Python 0137-single-number-ii.py 
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ans = 0
        for i in range(32):
            cntBit1 = 0
            for num in nums:
                if (num >> i) & 1:
                    cntBit1 += 1
            cntBit1 %= 3
            if cntBit1:
                ans |= 1 << i
               
        return ans - (1 << 32) if ans > (1 << 31) - 1 else ans