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

chắc lại dùng giá trị của mảng cần xét làm index của mảng đếm ạ?

đang cần mọi người cho lời giải, sao lại đi hỏi ngược người ra đề :’(

Em không biết nhiều về thuật toán, càng không biết tính độ phức tạp của thuật toán thế nào . Thôi thì em cứ nêu quan điểm của mình vậy, có gì sai mong mọi người chỉ giáo .

Em nghĩ là minh có thể tạo ra một mảng để chứa các phần tử xuất hiện lẻ lần (mảng 2), vì chỉ có 2 phần tử xuất hiện lẻ lần nên kích thước chỉ cần bằng nửa mảng đã cho (mảng 1) thôi. Duyệt từng phần tử trong mảng 1; nếu chưa có trong mảng 2 thì thêm vào; có rồi thì xóa đi.

Code này có được tính là O(n) không?

Trường hợp xấu nhất là O(n + n) => O(n)
Trường hợp tốt nhất là O(n + 2) => O(n)
Trường hợp average là O(n + n/2) => 0(n)

1. Dùng dic đếm.
2. In thằng nào lẻ, improve một chút là có thêm một cái cờ, in đủ 2 thằng thì quit luôn

Đang luyện Python, nên code bằng Python luôn

import collections

n = raw_input()
arr = raw_input().split()

def solution(arr, n):
	dic = collections.defaultdict(int)
	for num in arr:
		dic[num] += 1
	printed = 0
	for num,count in dic.items():
		if printed == 2:
			break
		if count & 1:
			printed += 1
			print num
	pass

solution(arr, n)

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

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?

Nghỉ thế này đây, chưa làm
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).

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é

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;
        }
    }
}

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?

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;

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

Đây nè anh @nxphuc ơi

Hôm nay lướt trên Facebook, em lượm được 1 bài như sau: Cho một mảng số nguyên N phần tử, mỗi phần tử xuất hiện 2 lần, chỉ riêng có HAI phần tử xuất hiện 1 lần duy nhất, yêu cầu tìm ra 2 phần tử đó. Ví dụ: [2, 5, 1, 4, 3, 5, 3, 2] --> kết quả [1, 4] Kì vọng: O(N) time và O(1) extra space complexity. Mọi người cùng suy nghĩ làm cho vui nhé! HINT: xử lý bit, XOR, bit khác nhau

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

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

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

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ẻ

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

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

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

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

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

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é