Tìm Các Phần Tử Giao Nhau Của Hai Mảng Đã Được Sắp Xếp Trong JavaScript

Để tìm các phần tử giao nhau của hai mảng đã được sắp xếp trong JavaScript, bạn có thể sử dụng phương pháp duyệt đồng thời (two-pointer technique). Phương pháp này rất hiệu quả vì nó khai thác tính chất đã sắp xếp của các mảng để tối ưu hóa quá trình tìm kiếm.

Mã Nguồn:

function intersectionOfSortedArrays(arr1, arr2) {
    let i = 0, j = 0;
    let intersection = [];

    // Duyệt đồng thời qua cả hai mảng
    while (i < arr1.length && j < arr2.length) {
        if (arr1[i] < arr2[j]) {
            i++;
        } else if (arr1[i] > arr2[j]) {
            j++;
        } else {
            // Nếu phần tử giống nhau, thêm vào kết quả
            intersection.push(arr1[i]);
            i++;
            j++;
        }
    }

    return intersection;
}

// Ví dụ kiểm tra
console.log(intersectionOfSortedArrays([1, 3, 4, 5, 7], [2, 3, 5, 6])); // [3, 5]
console.log(intersectionOfSortedArrays([2, 5, 6], [4, 5, 6, 7])); // [5, 6]

Giải Thích:

1. Khởi Tạo Con Trỏ:

   • i và j được khởi tạo bằng 0, đại diện cho vị trí hiện tại trong arr1 và arr2.

2. Duyệt Qua Cả Hai Mảng:

   • Trong khi cả hai con trỏ chưa vượt quá độ dài của các mảng, so sánh các phần tử tại vị trí i và j.
   • Nếu arr1[i] nhỏ hơn arr2[j], tăng con trỏ i.
   • Nếu arr1[i] lớn hơn arr2[j], tăng con trỏ j.
   • Nếu arr1[i] bằng arr2[j], thêm phần tử đó vào mảng kết quả và tăng cả hai con trỏ i và j.

3. Trả Về Kết Quả:

   • Mảng intersection chứa các phần tử giao nhau của arr1 và arr2.

Tổng Quan:

• Two-pointer Technique: Hiệu quả trong việc tìm giao của các mảng đã được sắp xếp với độ phức tạp thời gian O(n + m), trong đó n và m là độ dài của hai mảng.
• Ứng Dụng: Thích hợp cho các bài toán liên quan đến xử lý dữ liệu đã được sắp xếp, tối ưu hóa thời gian chạy.

Ví Dụ Thực Tế:

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

Trong ví dụ trên, mảng [1, 3, 4, 5, 7] và mảng [2, 3, 5, 6] có các phần tử giao nhau là [3, 5], và mảng [2, 5, 6] và [4, 5, 6, 7] có các phần tử giao nhau là [5, 6].