Bạn có chắc chắn muốn xóa bài viết này không ?
Bạn có chắc chắn muốn xóa bình luận này không ?
Sử dụng toán tử XOR
Toán tử XOR có tính chất:
- A XOR A = 0
- 0 XOR A = A
Với tính chất này, có thể cài đặt bài toán sau với độ phức tạp O(N) về run-time, và với O(1) về space.
Bài toán:
Cho một mảng có N số, với N là số lẻ. Mỗi phần tử trong mảng đều có 1 phần tử tương ứng với giá trị bằng chính nó, chỉ trừ đúng 1 phần tử duy nhất không có tính chất này.
Viết chương trình tìm phần tử đó
def solution(A):
result = 0
for item in A:
result = result ^ item
return result
Cách cài đặt thông thường, sử dụng hash table, để đếm số lượng các phần tử, vẫn có độ phức tạp O(N)
def solution(A):
counter = {}
for elem in A:
if elem not in counter:
counter[elem] = 0
counter[elem] += 1
for key, value in counter.iteritems():
if value % 2 == 1:
return key
Mở rộng bài toán
Bài toán sử dụng XOR có thể bắt nguồn từ bài toán sau
Cho một số K và một mảng có N số, với N là số lẻ. Mỗi phần tử X trong mảng đều có 1 phần tử tương ứng với giá trị bằng K - X, chỉ trừ đúng 1 phần tử duy nhất không có tính chất này.
Viết chương trình tìm phần tử đó
Tư tưởng thì cũng làm như bài toán trên, ta cần tìm một phép toán để khử đi giá trị
kiennt 09-10-2016






