Đề bài

Cho 1 mảng với N + 1 số từ 1 đến N hãy tìm ra 2 số trùng nhau với điều kiện:

1. Độ phức tạp nhỏ hơn O(N^2).
2. Không làm thay đổi thứ tự các số trong mảng.
3. Tiết kiệm bộ nhớ, tốt nhất là không sinh ra mảng mới.

Lời giải

Cách 1: Sử dụng Map

Như chúng ta đã biết , vì map đảm bảo tính duy nhất cho một key, nên chúng ta có thể coi mỗi số là một key, chúng ta sẽ ánh xạ với số lần số đó xuất hiện trong mảng, nếu số nào có số lần xuất hiện lớn hơn 1 nghĩa là số đó bị trùng:

function findAllDuplicates(arr) {
    const freq = new Map();
    
    for (const v of arr) {
        freq.set(v, (freq.get(v) || 0) + 1);
    }

    const duplicates = [];
    for (const [value, count] of freq.entries()) {
        if (count >= 2) {
            duplicates.push(value);
        }
    }

    return duplicates;
}

const arr = [1, 5, 5, 3, 2, 4];
console.log("Mảng:", arr);
console.log("Các số bị trùng:", findAllDuplicates(arr));

// Kết quả
Mảng: (6) [1, 5, 5, 3, 2, 4]
Các số bị trùng: [5]

Cách này có vẻ ổn, tuy nhiên nó lại sinh ra mảng mới (vì bản chất bên trong map sử dụng mảng) nên nó có thể vi phạm vào điều kiện thứ 3 là tiết kiệm bộ nhớ.

Cách 2: Sắp xếp rồi tìm 2 số liền kề

Ý tưởng là chúng ta sẽ sử dụng thuật toán sắp xếp (nhanh nhất là quick sort với độ phức tạp là O(n log n), sau đó chỉ cần so sánh 2 số liền kề là xong:

function findAllDuplicatesSorted(arr) {
    const a = [...arr].sort((x, y) => x - y);

    const duplicates = [];
    for (let i = 1; i < a.length; i++) {
        if (a[i] === a[i - 1]) {
            if (duplicates[duplicates.length - 1] !== a[i]) {
                duplicates.push(a[i]);
            }
        }
    }

    return duplicates;
}

const arr = [1, 5, 5, 3, 2, 4];
console.log("Mảng:", arr);
console.log("Các số bị trùng (sort):", findAllDuplicatesSorted(arr));

// Kết quả
Mảng: (6) [1, 5, 5, 3, 2, 4]
Các số bị trùng (sort): [5]

Cách này cũng có vẻ ổn nhưng nó cần phải tạo thêm mảng mới, tốc độ thậm chí còn chậm hơn cả dùng map.

Cách 3: Sử dụng thuật toán Floyd.

Trong thuật toán này chúng ta sẽ thông qua câu chuyện chạy đua giữ rùa và thỏ kinh điển. Hãy nói chúng ta sẽ tổ chức dãy số (arr) thành một đường đua, ở mỗi điểm sẽ có số và thứ tự (index) của số đó:

1[0], 5[1], 5[2], 3[3], 2[4], 4[5]

Đầu tiên hãy nói về rùa, vì rùa chạy chậm nên mỗi lần chỉ đi một "một bước", một bước ở đây có nghĩa là số tại điểm mà nó đã đến sẽ là index của điểm tiếp theo (arr[index]), hãy liệt kê từng bước của rùa:

Rùa xuất phát điểm tại arr[0] = 1.

Bước 1: Điểm mà rùa sẽ đến là arr[1] = 5.

Bước 2: Điểm mà rùa sẽ đến là arr[5] = 4.

Bước 3: Điểm mà rùa sẽ đến là arr[4] = 2.

Bước 4: Điểm mà rùa sẽ đến là arr[2] = 5.

Bước 5: Điểm mà rùa sẽ đến là arr[5] = 4.

5, 4, 2, 5, 4

Tiếp theo hãy nói về thỏ, thỏ có thể chạy rất nhanh nên thỏ có thể chạy "hai bước", hai bước ở đây có nghĩa là:

Bước 1: Số tại điểm mà nó đã đến sẽ là index của điểm tiếp theo (arr[index]).

Bước 2: Từ index ở bước 1 lại nhảy thêm một bước nữa (arr[arr[index]]).

Hãy liệt kê từng bước mà thỏ sẽ chạy để bạn hình dung rõ hơn:

Thỏ xuất phát điểm tại arr[0] = 1.

Bước 1: Điểm mà thỏ sẽ đến là arr[arr[1]] = arr[5] = 4.

Bước 2: Điểm mà thỏ sẽ đến là arr[arr[4]] = arr[2] = 5.

Bước 3: Điểm mà thỏ sẽ đến là arr[arr[5]] = arr[4] = 2.

Bước 4: Điểm mà thỏ sẽ đến là arr[arr[2]] = arr[5] = 4.

Bước 5: Điểm mà thỏ sẽ đến là arr[arr[4]] = arr[2] = 5.

Viết thành dãy các số của từng bước sẽ là:

4, 5, 2, 4, 5

Như bạn thấy sau 3 bước rùa và thỏ sẽ gặp nhau ở điểm có số bằng 2 (index = 4).

Bây giờ hãy cho rùa quay trở lại vạch xuất phát (arr[0] = 1) và cả rùa và thỏ mỗi con đi mỗi bước 1 lần:

Ta sẽ có các bước:

Bước 1:

• Rùa sẽ đến điểm arr[1] = 5.
• Thỏ sẽ đến điểm arr[2] = 5.

Ta thấy cả rùa và thỏ đều đến điểm có số là 5 và 5 chính là số trùng mà chúng ta cần tìm.

Tóm gọn lại thì thuật toán Floyd gồm 2 pha:

Pha 1: Thỏ & rùa gặp nhau trong vòng

• Rùa đi 1 bước mỗi lần.
• Thỏ đi 2 bước mỗi lần.

Vì có vòng (có số trùng nhau) nên kiểu gì cũng gặp nhau trong vòng.

Pha 2: Tìm điểm bắt đầu vòng = số trùng

• Cho rùa quay về đầu mảng.
• Cả rùa và thỏ cùng đi mỗi lần 1 bước.

Chúng sẽ gặp nhau tại điểm bắt đầu vòng, cũng chính là số trùng.

Thuật toán được cài đặt như sau:

function findDuplicate(nums) {
    // Phase 1: Thỏ và rùa gặp nhau
    let tortoise = nums[0];
    let hare = nums[0];

    do {
        tortoise = nums[tortoise]; 
        hare = nums[nums[hare]];
    } while (tortoise !== hare);

    // Phase 2: Tìm điểm bắt đầu vòng = số trùng
    tortoise = nums[0];
    while (tortoise !== hare) {
        tortoise = nums[tortoise];
        hare = nums[hare];
    }

    return hare; // hoặc tortoise, lúc này chúng bằng nhau
}

const arr = [1, 5, 5, 3, 2, 4];
console.log("Số bị trùng là:", findDuplicate(arr));

// Kết quả: 
Số bị trùng là: 5

Cách này là ổn nhất, không phải tạo mảng mới, mức độ thuật toán O(n).