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

#1

Theo đề nghị của anh Đạt (@ltd), cũng góp 1 bài cho vui, có thể là có người sẽ gặp rồi :slight_smile:
Cho một mảng số nguyên N phần tử (N chẵn), mỗi phần tử xuất hiện chẵn lần, chỉ riêng có đúng hai phần tử xuất hiện lẻ lần.
Hãy tìm ra 2 phần tử đó.
Ví dụ:
Input

8
2 5 1 4 3 5 3 2

Output

1 4

Lưu ý giá trị các phần tử trong mảng là số nguyên 32 bit.

Được sử dụng mọi ngôn ngữ, nhưng khuyến khích các bạn chỉ cần đưa ra thuật toán, mô tả giải thích bằng lời, không cần cài đặt, như vậy mọi người đều có thể hiểu thuật toán (vì đôi khi một số bạn có thể không biết Java, python, hay thậm chí là Brainf**k :joy: )

Kỳ vọng: liệu có thể giải quyết bài toán trong O(N) time + O(1) extra space complexity

2 Likes
#2

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

#3

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

#4

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 :joy:. 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 :innocent:.

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.

#5

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)
#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

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