Tìm phần tử trùng lặp trong dãy n số đầu tiên JavaScript

Tìm số trùng lặp trong mảng 1..n có n+1 phần tử

Cho mảng chứa các số từ 1 đến n, nhưng có **một số xuất hiện 2 lần** (tổng n+1 phần tử). Tìm số đó trong **O(n) time, O(1) space**.

Phương pháp 1: Toán học với reduce() (Thông minh nhất)

const arr = [1, 4, 8, 5, 6, 7, 9, 2, 3, 7]; // n=9, 10 phần tử

// Công thức: duplicate = sum(arr) - sum(1..n)
// sum(1..n) = n*(n+1)/2, nhưng mảng length = n+1
// => n = arr.length - 1
const duplicate = arr => {
    const n = arr.length - 1;
    const sum = arr.reduce((a, b) => a + b, 0);
    const expectedSum = n * (n + 1) / 2;
    return sum - expectedSum;
};

console.log(duplicate(arr)); // 7

Giải thích thuật toán reduce gốc (từ bài)

const duplicate = a => 
    a.reduce((acc, val, ind) => val + acc - (ind + 1)) + a.length - 1;

// Trace với [2, 3, 1, 2] (n=3, length=4)
// reduce callback chạy từ index 1 (vì không có initialValue)
// acc khởi tạo = a[0] = 2

// i=1: val=3, ind=1  → acc = 2 + 3 - (1+1) = 3
// i=2: val=1, ind=2  → acc = 3 + 1 - (2+1) = 1
// i=3: val=2, ind=3  → acc = 1 + 2 - (3+1) = -1
// Kết quả reduce = -1
// + a.length - 1 = -1 + 4 - 1 = 2 ✓

Phương pháp 2: forEach + Toán học (Dễ hiểu hơn)

const duplicate = a => {
    let sum = 0;
    const n = a.length; // n+1 phần tử
    a.forEach(num => sum += num);
    // Tổng 1..(n-1) = (n-1)*n/2
    return sum - (n * (n - 1) / 2);
};

console.log(duplicate([1,4,8,5,6,7,9,2,3,7])); // 7

Phương pháp 3: Set (O(n) space - dễ hiểu)

const duplicate = arr => {
    const seen = new Set();
    for (const num of arr) {
        if (seen.has(num)) return num;
        seen.add(num);
    }
};
// O(n) time, O(n) space

Phương pháp 4: Floyd's Tortoise and Hare (O(1) space, không sửa mảng)

// Chỉ dùng khi mảng chứa 1..n và có thể dùng giá trị làm index
const findDuplicate = nums => {
    // Phase 1: Tìm intersection
    let slow = nums[0], fast = nums[0];
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow !== fast);
    
    // Phase 2: Tìm entrance của cycle
    slow = nums[0];
    while (slow !== fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    return slow;
};

Phương pháp 5: Sửa mảng (Negative marking) - O(1) space

const findDuplicate = nums => {
    for (let i = 0; i < nums.length; i++) {
        const index = Math.abs(nums[i]);
        if (nums[index] < 0) return index;
        nums[index] = -nums[index];
    }
};
// LƯU Ý: Làm thay đổi mảng gốc

So sánh

Lưu ý

• Phương pháp toán học chỉ đúng khi **duy nhất 1 số bị trùng 2 lần**, các số còn lại xuất hiện 1 lần.
• Nếu có nhiều số trùng hoặc trùng >2 lần, cần dùng Set hoặc sort.
• Đối với mảng lớn, tránh indexOf trong reduce (O(n²)).