Single Number
Bạn có một danh sách nums, trong đó mỗi giá trị xuất hiện đúng hai lần, ngoại trừ một giá trị chỉ xuất hiện một lần. Hãy trả về giá trị chỉ xuất hiện một lần.
Hàm
- numsinteger-array
- a danh sách trong đó mỗi giá trị xuất hiện hai lần, ngoại trừ một giá trị
- Trả vềinteger
- giá trị chỉ xuất hiện một lần
Ràng buộc
1 ≤ nums.length < 104-104 ≤ nums[i] ≤ 104- Mỗi giá trị xuất hiện đúng hai lần, ngoại trừ một giá trị chỉ xuất hiện đúng một lần.
Ví dụ
- Đầu vào
- nums = [8, 3, 8]
- Đầu ra
- 3
- Giải thích
- 8 xuất hiện hai lần và 3 xuất hiện một lần, nên đáp án là 3.
- Đầu vào
- nums = [5, -2, 7, 5, 7]
- Đầu ra
- -2
- Giải thích
- 5 và 7 đều xuất hiện hai lần, còn -2 là giá trị duy nhất chỉ xuất hiện một lần.
- Đầu vào
- nums = [42]
- Đầu ra
- 42
- Giải thích
- Danh sách chỉ có một giá trị thì không có cặp nào, vì vậy giá trị đó là đáp án.
Câu hỏi mở rộng
Điều gì xảy ra nếu mỗi giá trị xuất hiện ba lần, trừ một giá trị? Chỉ XOR thôi không thể khử các bộ ba nữa. Bạn vẫn có thể tìm giá trị đơn lẻ trong thời gian O(n) và dùng thêm O(1) bộ nhớ không?
Gợi ý
Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.
Nếu mọi cặp giá trị bằng nhau đều biến mất, chỉ còn lại đáp án. Có phép toán nào biến hai số bằng nhau thành không có gì không?
XOR cho kết quả:
x ^ xlà0vàx ^ 0làx. XOR cũng không phụ thuộc vào thứ tự, nên hai bản sao của một giá trị không cần nằm cạnh nhau để triệt tiêu.Giữ một biến bắt đầu bằng
0. XOR từng giá trị củanumsvào biến đó, rồi trả về biến đó. Không cần dùng map hay sắp xếp.
Lời giải
Bản đồ băm tìm giá trị không có cặp bằng cách đếm, nhưng bản đồ sẽ lớn lên cùng danh sách. XOR không cần đếm, vì một giá trị XOR với chính nó sẽ cho ra 0. XOR toàn bộ danh sách với nhau, mỗi cặp sẽ tự triệt tiêu, để lại giá trị duy nhất trong một biến.
Đếm từng giá trị bằng cách quét
Đúng, nhưng không chạy xong với các test lớn nhất
Ý tưởng
Với mỗi giá trị, hãy duyệt toàn bộ danh sách và đếm số lần giá trị đó xuất hiện. Trả về giá trị đầu tiên có số lần xuất hiện là 1. Cách đếm này tuân theo định nghĩa của đáp án, nên kết quả là chính xác. Mỗi trong số n giá trị đều kích hoạt một lần duyệt qua n giá trị: gần 10^8 phép so sánh khi giá trị chỉ xuất hiện một lần nằm ở cuối danh sách có 9,999 phần tử.
Thuật toán
- Lặp qua từng giá trị trong
nums. - Quét toàn bộ danh sách và đếm các giá trị bằng giá trị đó.
- Nếu số lượng là 1, trả về giá trị đó.
def singleNumber(nums):
for value in nums:
# count() scans the whole list: O(n) per value.
if nums.count(value) == 1:
return value
return 0Đếm bằng bảng băm
Ý tưởng
Đếm số lần xuất hiện của mỗi giá trị trong một lượt bằng cách dùng bảng băm ánh xạ giá trị sang số lần xuất hiện. Với [5, -2, 7, 5, 7], bảng kết thúc với các mục 5 → 2, -2 → 1, 7 → 2, và lượt duyệt qua bảng sẽ tìm thấy -2.
Mỗi giá trị cần một lần cập nhật bảng, nên độ phức tạp thời gian là O(n). Bảng chứa khoảng n/2 mục, cần thêm O(n) bộ nhớ. C không có bảng ánh xạ tích hợp sẵn, nên một mảng bộ đếm với chỉ số value + 10^4 sẽ đảm nhiệm vai trò đó.
Thuật toán
- Tạo một map rỗng để lưu giá trị và số lần xuất hiện.
- Với mỗi giá trị trong
nums, tăng số lần xuất hiện của giá trị đó lên 1. - Duyệt qua map và trả về giá trị có số lần xuất hiện là 1.
def singleNumber(nums):
counts = {}
for value in nums:
counts[value] = counts.get(value, 0) + 1
for value, count in counts.items():
if count == 1:
return value
return 0XOR tất cả các giá trị
Ý tưởng
XOR đặt bit thành 1 khi hai đầu vào khác nhau. Vì vậy, x ^ x = 0, x ^ 0 = x, và thứ tự các phép toán không quan trọng.
Thực hiện XOR với toàn bộ danh sách trong một biến bắt đầu bằng 0. Nhóm lại các phép toán để mỗi giá trị gặp giá trị giống nó: mỗi cặp cho kết quả 0, còn 0 ^ single giữ nguyên giá trị đơn lẻ. Với [8, 3, 8]: 0 ^ 8 = 8, sau đó 8 ^ 3 = 11, rồi 11 ^ 8 = 3. Vòng lặp đọc mỗi giá trị một lần và chỉ giữ một biến: thời gian O(n) và bộ nhớ phụ O(1).
Thuật toán
- Đặt
resultthành 0. - Với mỗi giá trị trong
nums, đặtresultthànhresult ^ value. - Trả về
result.
def singleNumber(nums):
result = 0
for value in nums:
result ^= value
return result
Lỗi thường gặp và trường hợp biên
- Bắt đầu
resulttạinums[0], rồi lặp qua mọi giá trị, kể cả chỉ số 0. Giá trị đầu tiên được XOR hai lần nên triệt tiêu lẫn nhau. Hãy bắt đầu từ 0 hoặc bỏ qua chỉ số 0. - Sắp xếp rồi so sánh các phần tử liền kề theo từng cặp, sau đó quên mất rằng giá trị duy nhất có thể nằm cuối danh sách. Trong
[1, 1, 2], mọi cặp được kiểm tra đều khớp nhau, và đáp án là số 2 còn lại. - Dùng lại vòng lặp XOR khi các giá trị có thể xuất hiện số lần lẻ. XOR chỉ triệt tiêu các số lần xuất hiện chẵn, nên với
[4, 4, 4, 9], kết quả là4 ^ 9 = 13, không phải 9.
Câu hỏi thường gặp3
Độ phức tạp thời gian của Single Number là bao nhiêu?
Lời giải XOR chạy trong thời gian O(n) và dùng thêm O(1) bộ nhớ. Bản đồ băm cũng chạy trong thời gian O(n) nhưng cần O(n) bộ nhớ. Đếm từng giá trị bằng cách quét lại từ đầu cần O(n²).
Cách giải XOR có hoạt động với số âm không?
Đúng. XOR hoạt động trên các bit lưu trữ số, còn số âm được lưu dưới dạng bù hai. Hai số âm bằng nhau có các bit giống hệt nhau, nên chúng triệt tiêu nhau giống như số dương. Trong [5, -2, 7, 5, 7], kết quả là -2.
Bạn có thể giải bài toán số đơn lẻ bằng phép tính tổng thay vì XOR không?
Đúng. 2 × sum(distinct values) - sum(nums) là giá trị duy nhất: mỗi giá trị theo cặp được cộng hai lần ở cả hai vế, còn giá trị đơn lẻ được cộng hai lần ở một vế và một lần ở vế kia. Với [5, -2, 7, 5, 7], ta có 2 × 10 - 22 = -2. Tập hợp các giá trị riêng biệt cần bộ nhớ O(n), còn XOR thì không.
Bài tập tương tự
Các bài tập dùng cùng ý tưởng. Giải hai hoặc ba bài là bạn sẽ nhớ được mẫu này.
def singleNumber(nums):
# Viết code ở đâyKiểm thử #1
Kiểm thử #2
Kiểm thử #3
Đối số
nums = [8, 3, 8]
Đầu ra mong đợi
3