Leetcode - Single Number

#1

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Luật chơi: Các bạn chỉ nên post code lên http://ideone.com/, ai muốn xem thì click vào xem. Không nên post trực tiếp lên mất hay ^^

Nhớ post kèm ngôn ngữ và thời gian thực thi nhé :smile:

Tổng hợp Leetcode
#2

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 :confused:

#3

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)

#4

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á

#5

Chạy mất 48ms :blush:

3 Likes
#6

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

4 Likes
#7

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

1 Like
#8

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


Cái link này share không thấy nó ra cái gì nhỉ?

368ms

1 Like
#9

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

1 Like
#10

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” :slight_smile:

3 Likes
#11

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

#12 
n ^= nums[i];

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

#13

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

2 Likes
#14

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

#15

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

#16

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.

4 Likes
#17

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

2 Likes
#18

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.

#19

Sorry, Thanks for your advice :smiley:

#20

Đạ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ó.

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?