137. Single Number II
Tags:
Medium
Skills:
Bitwise
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu tìm phần tử xuất hiện đúng một lần trong mảng, trong khi các phần tử khác xuất hiện đúng ba lần.
TC: O(n)
SC: O(1)
Approach - Bitwise Counting
Solution
1function singleNumber(nums: number[]): number {
2 let res =0
3 for(let i = 0; i < 32; i++) {
4 let sum = 0
5 for(const num of nums) sum += (num >> i) & 1
6 if(sum % 3 !== 0) res |= (1 << i)
7 }
8 return res | 0
9};Ví dụ minh họa
Giả sử num = 6 (nhị phân là 0000 0110):
num >> 0 = 0000 0110 (không đổi)num >> 1 = 0000 0011 (dịch phải 1 bit, thêm 0 vào bên trái)num >> 2 = 0000 0001 (dịch phải 2 bit, thêm 00 vào bên trái)(1 << i) nghĩa là gì?
...0001.1 << i), bạn sẽ tạo ra một số mà chỉ có bit thứ i là 1, còn lại đều là 0.Ví dụ:
1 << 0 = 0001 (bit 0 là 1)1 << 1 = 0010 (bit 1 là 1)1 << 2 = 0100 (bit 2 là 1)1 << 3 = 1000 (bit 3 là 1)res |= (1 << i) nghĩa là gì?|= là viết tắt của bitwise OR và gánMục đích
res lên 1 mà không làm thay đổi các bit khácVí dụ trực quan
Giả sử:
res = 0000 (tất cả bit là 0)Thực hiện:
(1 << 2) = 0100res | (1 << 2) = 0000 | 0100 = 0100res: res = 0100Nếu tiếp tục muốn bật bit thứ 0:
(1 << 0) = 0001res | (1 << 0) = 0100 | 0001 = 0101res: res = 0101res | 0 và res >>> 0 res | 0
res và 0 trên từng bitres là số âm, kết quả vẫn là số âmres >>> 0
res là số âm, kết quả sẽ thành một số dương rất lơn (vì bit dấu được fill thành 0)Ví dụ minh họa
Giả sử res = -1 (trong nhị phân 32-bit là toàn bộ bit 1):
res | 0 = -1 (giữ nguyên là số âm)res >>> 0 = 4294967295 (toàn bộ bit 1, nhưng là số dương không dấu lớn nhất trong 32 bit)