Tìm hai số xuất hiện lẻ lần trong mảng

#6

python chơi hỗ trợ dict O(N) thế này thì hết vui rồi :’(
nhưng mà ngôn ngữ khác thì sao anh, cách nào tương đương không

#7

A, anh dùng bitwise operator à? Dùng cái này có ưu điểm gì so với if count % 2 != 0 không hay chỉ ngắn hơn thôi hả anh?

#8

Nghỉ thế này đây, chưa làm :smiley:
Dùng radix sort: độ phưc tạp : O(2mn) = O(n)
loop để check a[i]!=a[i+1], nếu khác check xem nếu i là chẳn, thì số đó xuất hiện lẽ lần, đánh dấu tại vị trí i+1 rồi xét tiếp: O(n).

#9

phép toán xử lý bit (bitwise operator) nhanh hơn các biểu thức luận lý và số học nhé

#10

C++ cũng hỗ trợ unordered_map, làm cũng tương tự. Mà anh code C++ quen tay hơn.

Bài này có thể tận dụng luôn lúc nhập dữ liệu vào để nhập thẳng vào cái unordered_map luôn cũng được. Nhưng coi như là phần nhập liệu với phần tính toán là 2 phần riêng lẻ.

#include <iostream>
#include <unordered_map>
#include <vector>
#include <stdio.h>

using namespace std;

int main() {
    freopen("input.txt", "r", stdin);
    int n;
    cin >> n;
    vector<int> v(n);
    for(int i = 0; i < n; ++i) {
        cin >> v[i];
    }

    unordered_map<int, int> map;
    for(int i : v)
        map[i]++;

    int printed = 0;
    for(auto m : map) {
        if (m.second & 1) {
            cout << m.first << endl;
            if(++printed == 2)
                break;
        }
    }
}

nếu em dùng count & 1 thì nó vừa ngắn hơn, vừa nhanh hơn.

với count % 2 != 0 em làm 2 thao tác. Chia lấy dư và so sánh. Cái nào cũng chậm cả.

Với count & 1 thì em chỉ có một thao tác là bitwise and, nhanh hơn nhiều.

@Luong_Quang_Manh Với Python thì làm sao để viết thế này nhỉ:

if(++printed == 2)
    break;
#11

:grin:
nhưng liệu có cách nào mà vừa O(N) time và O(1) extra space không anh, dùng unordered_map thì O(N) extra space rồi

#12

Đây nè anh @nxphuc ơi :grin:

#13

Python đỡ được hàng đống thứ thì lại không có increment and decrement operators. Trade-off cả :grimacing:

#14

Group lập trình của anh Sơn đúng không :3
thì người đăng là tại hạ mà :))

2 Likes
#16

Làm gì tới O(N) space complexity, mảng này duplicate nhiều mà :slight_smile:

Còn vụ O(1) extra space thì chưa nghĩ ra, lúc chiều nghĩ hoài không ra nên ngồi học Python. Thấy code tí Python cho nó quen tay nên post solution này.

Nếu trường hợp là mảng chỉ có 1 số lẻ thì khỏe rồi, dùng xor

int main() {
    freopen("input.txt", "r", stdin);
    int n;
    cin >> n;
    vector<int> v(n);
    for(int i = 0; i < n; ++i) {
        cin >> v[i];
    }

    int ans = 0;
    for(int i : v)
        ans ^= i;
    cout << ans;
}

Với input

7
2 5 1 3 5 3 2

Output

1

Chắc phải có mấu chốt nào đấy giống như bài 1 số lẻ :thinking:

#17

trường hợp xấu nhất thì là O((N-2)/2) cũng xem như O(N) rồi còn gì anh :smiley:

1 Like
#18

yup, mấu chốt là ở cái XOR

1 Like
#19

Gọi 2 số cần tìm là x,y
thì kết quả tổng xor của n số = x xor y =s
do x !=y nên x xor y khác 0, => pick 1 bit 1 bất kỳ của s (gọi là bit j) thì chia được tập thành 2 tập (1 tập chứa bit j, 1 tập ko chứa bit j) , rồi xor trong mỗi tập thì được 1 số
p/s: O(n) time thì okie còn O(1) space thì chắc đọc file 2 lần quá :))
p/s 2: O(1) extra space :3

#20

Cách của bạn cũng là O(1) space mà. Cách dùng xor là chuẩn O(n) time rồi

#21

tính đánh dấu solve rồi, mà tự bạn nói bạn không phải O(1) nên thôi nghỉ :3

#22

Nếu không đọc file 2 lần thì bạn vẫn cần dùng 1 mảng n phần tử để lưu lại các phần tử để duyệt lại lần thứ 2 nhé

#23

Bạn viết hàm để đưa ra thuật toán thì không tính phần input đọc file bạn nhé. void solve(int* a, int n). Trừ khi đó là giải thuật đọc file thì lại khác.

1 Like
#24

extra space bạn ơi :3

#25

ồ đọc thiếu :smiley: thế thì okie rồi đó

#26

ừm mình quen tính kiểu tìm thuật để giải nguyên bài rồi :smiley:

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