Sử dụng toán tử XOR
TIL
490
White

kiennt viết ngày 10/10/2016

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

Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

White

kiennt

29 bài viết.
228 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
81 18
Mọi chuyện bắt đầu từ nắm 2013 trong quá trình xây dựng chức năng login với Facebook, tôi đã tìm ra một cách để tấn công vào các hệ thống login với...
kiennt viết gần 2 năm trước
81 18
White
26 5
1. Đặt vấn đề Một trong các vấn đề của một hệ thống backend là bài toán điều phối request tới các nguồn dữ liệu. Xét bài toán với một hệ thống bl...
kiennt viết hơn 1 năm trước
26 5
White
22 4
Mở đầu Tôi đang học về (Link) (Link) (hệ thống phân tán). Đây là một lĩnh vực rất hay và khó (đối với tôi). Phần lớn các hệ thống máy tính hiện na...
kiennt viết hơn 1 năm trước
22 4
Bài viết liên quan
White
1 1
Chào mọi người, hôm nay mình viết một bài TIL nhỏ về cách lấy độ phân giải của màn hình hiện tại đang sử dụng. xdpyinfo | grep dimensions Kết quả...
namtx viết 7 tháng trước
1 1
White
8 0
Lấy fake path của file trong html input Ngữ cảnh: em cần làm một cái nút tải ảnh lên có preview. GIải pháp đầu: Dùng (Link) đọc file ảnh thành ba...
Hoàng Duy viết gần 2 năm trước
8 0
White
2 2
Bash script to fast serve Laravel project Lười gõ dòng lệnh quá nên tạo ra cái script để gõ nhanh :D laravelstart.sh /bin/bash if z "$1" ] ...
Vũ Hoàng Chung viết 11 tháng trước
2 2
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


White
{{userFollowed ? 'Following' : 'Follow'}}
29 bài viết.
228 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!