[Thuật toán] Tìm phần tử chỉ xuất hiện 1 lần trong mảng (các phần tử khác xuất hiện 2 lần)

Bài này tớ bếch từ GeeksForGeeks về: https://www.geeksforgeeks.org/find-element-appears-array-every-element-appears-twice/

Đề bài

Cho 1 mảng các số nguyên dương. Các phần tử đều xuất hiện 2 lần, chỉ duy nhất 1 phần tử xuất hiện 1 lần. Hãy tìm thằng lạc loài đó

Hướng xử lý

Có 4 cách:

• Cách 1: Dùng 2 vòng for lồng nhau. Check thằng nào chỉ xuất hiện 1 lần thì trả về -> độ phức tạp O(n^2)
• Cách 2: Dùng 1 cái hashmap. For qua 1 lượt để đánh dấu số lần xuất hiện. For lại lượt nữa để tìm thằng nào chỉ xuất hiện 1 lần.
• Cách 3: Dùng tính chất phép XOR. a^a = 0 => xor tất cả với nhau sẽ tìm ra được thằng nào xuất hiện lẻ lần => cách này có vẻ xịn nhất, ít tốn bộ nhớ.
• Cách 4: Tính tổng các số xuất hiện 1 lần, nhân đôi lên rồi trừ đi tổng của dãy sẽ lòi ra thằng xuất hiện 1 lần –> cách này cũng thú vị, không dùng nhiều vòng lặp

Cách 1: Hơi lởm :v

Độ phức tạp O(n^2). Cách dành cho người mới học lập trình

	func solution1(arr []int) int {
	mainLoop:
	for i := 0; i < len(arr); i++ {
	pivot := arr[i]
	for j := 0; j < i; j++ {
	if arr[j] == pivot {
	continue mainLoop
	}
	}
	for j := i + 1; j < len(arr); j++ {
	if arr[j] == pivot {
	continue mainLoop
	}
	}
	return pivot
	}
	return -1
	}

view raw find_not_duplicate_number_sol1.go hosted with ❤ by GitHub

Cách 2: Xịn hơn tí

Cách này độ phức tạp là O(n). Vẫn cần 2 lần dùng vòng lặp. Nhưng mà code dễ đọc, dễ maintain.

	func solution2(arr []int) int {
	mapCheck := make(map[int]int)
	for _, item := range arr {
	mapCheck[item]++
	}
	for number, value := range mapCheck {
	if value == 1 {
	return number
	}
	}
	return -1
	}

view raw find_not_duplicate_number_sol2.go hosted with ❤ by GitHub

Cách 3: Xịn nhất

	func solution3(arr []int) int {
	var result int
	for _, item := range arr {
	result = result^item
	}
	return result
	}

view raw find_not_duplicate_number_sol3.go hosted with ❤ by GitHub

Cách 4: Cũng được

	func solution4(arr []int) int {
	var sumSingle, sumAll int
	mapCheck := make(map[int]bool)
	for _, item := range arr {
	if _, ok := mapCheck[item]; !ok {
	sumSingle += item
	mapCheck[item] = true
	}
	sumAll += item
	}
	return sumSingle*2 – sumAll
	}

view raw find_not_duplicate_number_sol4.go hosted with ❤ by GitHub

Cảm ơn bạn đã đọc bài.

Chúc bạn một ngày làm việc hiệu quả ^^