Leetcode - Single Number

Tiếng anh e không rành lắm nhưng đại loại là nó bảo tìm ra 1 số đơn trong một dãy số ( mỗi số xuất hiện 2 lần thành một cặp ). Và phần lưu ý em không biết dịch sao luôn chỉ hiểu sơ sơ là áp dụng mà không sử dụng thêm bộ nhớ. Ai dịch giùm câu đầu với, google ra gì ấy chả hiểu

Nghĩa là thuật toán sử dụng có độ phức tạp tuyến tính (số phần tử càng lớn thì vẫn có độ phức tạp tương ứng, chứ ko như độ phức tạp O(n^3) gặp số phần tử lớn là số phép tính tăng vọt luôn)

Mình nghĩ là dựa vào sự chẵn lẻ và chia nhi phần, để code thử xem, đang ĐT nên khó code quá

Ideone.com

Ideone.com

Ideone is something more than a pastebin; it's an online compiler and debugging tool which allows to compile and run code online in more than 40 programming languages.

Chạy mất 48ms

Vào góp vui http://ideone.com/K6OsLM

Phép toán thần thánh :)) hay hay

Tại sao thằng Java nó lại chậm siêu mức chậm thế nhở?

leetcode.com

Account Login - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

Ideone.com

Ideone.com

Ideone is something more than a pastebin; it's an online compiler and debugging tool which allows to compile and run code online in more than 40 programming languages.

Không học thuật toán, cứ cách đơn giản nhất mà làm vậy
44ms

Ideone.com

Ideone.com

Ideone is something more than a pastebin; it's an online compiler and debugging tool which allows to compile and run code online in more than 40 programming languages.

Python: http://ideone.com/HpjEhC - 68 ms
C : http://ideone.com/V05MZf - 8 ms
Ruby : http://ideone.com/hrmJN6 - 92 ms
JS : http://ideone.com/gJBa4u - 144 ms

PS: Nhìn Ruby rất là “magic”

Mọi người nhớ post kèm ngôn ngữ mình chọn và thời gian thực thi nhé.

n ^= nums[i];  

Cho em hỏi khúc này nghĩa là sao ạ?

Nó là phép xor bit, xor n với phần tử thứ i của array nums.

Có ai làm bài này bằng C++ được 16ms không nhỉ?

Java: http://ideone.com/D7GCeu 1832nm --> wrong. Sorry all :d, please ignore the this link

Trong java dấu “^” là phép xor bit.

Phép xor là phép chỉ lấy giá trị true nếu hai vế của biểu thức có giá trị ngược nhau.

True ^ True == False
True ^ False == True
False ^ True == True
False ^ False == False

Phép này có một loạt các tính chất thú vị sau:

• Số 0 xor với bất kì số nào cũng ra chính số đó: 0^x==x (với mọi x)
• Hai số giống nhau xor với nhau chắc chắn ra 0: x^x==0 (với mọi x)
• Xor có tính chất kết hợp: a xor (b xor c) == (a xor b) xor c
• Tính chất thú vị nhất của xor là tính chất đảo ngược: a xor b == c thì a xor c == b
  Tính chất phía trên giúp phép xor có khả năng khôi phục văn bản gốc.

Ứng dụng của tính chất này là:

private void swap(int a, int b) { // Không cần dùng temp variable
    a = a ^ b;
    b = b ^ a; // b" == b ^ a" == b ^ a ^ b == a
    a = a ^ b; // a"" == b" ^ a" == a ^ a ^ b == b
}

Hoặc dùng cho bài toán check sum khi download… Nói chung là cứ làm về chủ đề giữ gìn văn bản gốc là ta nghĩ đến xor trước.

LOL, please submit your code to leetcode and get the result back.

Phân tích rất hay, trong bài này ứng dụng của phép toán này là nếu ta xor hai lần với số 0 thì ta có lại con số 0 xor n lần vời số 0 thì ta vẫn có lại số ban đầu, còn nếu xor 1 lần với số 0 thì ta có x, giá trị đứng một mình. Trong trường hợp giá trị đứng một mình là 0 thì giá trị trả về vẫn là 0.

Sorry, Thanks for your advice

Đạt viết nhầm rồi.

xor hai lần với số 0 thì ta có lại con số 0 ==> xor n lần vời số 0 thì ta vẫn có lại số ban đầu

Ứng dụng của xor trong bài này là 2 số bất kì xor với nhau đều bằng 0, số duy nhất không trùng xor với n số 0 ra chính nó.

À, Đạt viết nhầm, đúng như Cường nói.

xor n lần vời số 0 thì ta vẫn có lại số ban đầu

Đạt đang muốn nói về trường hợp khi n bắt đầu bằng 0 thì làm sao tìm ra được?

Với n == 0 và có 2 số 0 trong mảng

n ^= 0; // n == 0
n ^= 0; // n == 0

Khi đó mình sẽ xor tiếp cho đến khi tìm thấy số single

Với n==0 và có 1 số 0 trong mảng

n ^=0; // n == 0

Thì trường hợp có 1 số 0 trong mảng thì mình vẫn lòi ra được con số 0 này.