[Thuật toán] Tìm phần tử bị lặp lại từ 1 đến n-1

Bài này mình đọc và dịch từ GeeksForGeeks

Đề bài

Cho 1 mảng kích thước n (n > 0), chứa các số từ 1 đến n-1. Trong mảng có duy nhất 1 phần tử bị lặp lại. Tìm phần tử đó

Hướng xử lý

Có 5 cách

• Cách 1: Dùng 2 vòng for lồng nhau, check nếu thấy phần tử bị lặp lại thì return
• Cách 2: Dùng hashmap để đếm số lần xuất hiện. Thằng nào xuất hiện 2 lần thì in ra.
• Cách 3: Dùng tính chất của tổng: tổng từ 1 đến n là n*(n+1)/2 => tổng từ 1 đến n-1 là (n-1)*n/2. Phần tử bị lặp lại sẽ làm cho tổng của dãy dư ra 1 lượng đúng bằng phần tử đấy => lấy tổng dãy – (tổng từ 1 đến n – 1) là ra
• Cách 4: Dùng tính chất phép XOR: Vì dãy số liên tục từ 1 đến n-1 => (1^2^…^n-1) ^ (arr[0]^arr[1]^…arr[n-1]) sẽ ra đúng phần tử bị dư này.
• Cách 5: Dùng giá trị âm để đánh dấu lại.

Cách 1

Game khá dễ, không có gì để nói. Tuy nhiên độ phức tạp khá cao. Cách dành cho người mới học lập trình thôi.

	func sol1(arr []int) int {
	arrLen := len(arr)
	for i := 0; i < arrLen-1; i++ {
	for j := i + 1; j < arrLen; j++ {
	if arr[i] == arr[j] {
	return arr[i]
	}
	}
	}
	return -1
	}

view raw sol1.go hosted with ❤ by GitHub

Cách 2

Cũng dễ. Tạo 1 map đếm số lần xuất hiện. Sau đó for trong map, gặp phần tử nào có số lần xuất hiện > 1 => trả về luôn.

Cách này cũng chưa được tối ưu lắm. Độ phức tạp cũng vẫn cao.

	func sol2(arr []int) int {
	mapCheck := make(map[int]int)
	for i := 0; i < len(arr); i++ {
	mapCheck[arr[i]]++
	}
	for key, value := range mapCheck {
	if value > 1 {
	return key
	}
	}
	return -1
	}

view raw sol2.go hosted with ❤ by GitHub

Cách 3

Dùng tính chất phép công. Cách này khá tối ưu

Tổng dãy từ 1 đến n = n * (n+1)/2.

Dãy là các số từ 1 đến n – 1 => tổng = (n-1) * n / 2 (gọi tổng này là tổng 1)

Lại có 1 phần tử xuất hiện 2 lần => tổng mới = tổng 1 + phần tử xuất hiện 2 lần

=> phần tử xuất hiện 2 lần = tổng mới – tổng 1

	func sol3(arr []int, n int) int {
	sum := 0
	for i := 0; i < len(arr); i++ {
	sum += arr[i]
	}
	return sum – n*(n-1)/2
	}

view raw sol3.go hosted with ❤ by GitHub

Cách 4

Cách 4 thú vị nhất. Áp dụng tính chất XOR: a^a = 0

Giả sử dãy là a0, a1,…, an

=> (a0 ^ a1 ^… ^an) ^ (1 ^2^…^n-1) = phần tử bị dư.

Lí do là dãy có tính chất các số từ 1 đến n -1 chỉ xuất hiện 1 lần => khi XOR với gía trị index tương ứng sẽ ra 0 => kết quả lòi ra cuối cùng chính là phần tử xuất hiện 2 lần

Cách 5

Cũng khá hay, chỉ cần dùng 1 vòng lặp và 1 mảng đánh dấu.

Vì tính chất của mảng là các số nguyên không âm và có giá trị từ 1 -> n -1, ta tạo 1 mảng đánh dấu các giá trị gặp

• Tạo mảng arr2 có kích thước n
• Lặp trong arr ban đầu (arr1). Mỗi lần lặp check xem phần tử của arr2 có index = value của arr1 có giá trị âm không.
  • Nếu âm => đã xuất hiện rồi
  • Nếu không âm => chưa xuất hiện => đánh dấu arr2[item] = -2

	func sol5(arr []int) int {
	arr2 := make([]int, len(arr))
	for _, item := range arr {
	if arr2[item] < 0 {
	return item
	}
	arr2[item] = -2
	}
	return -1
	}

view raw sol5.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ả ^^