Chương trình C# tìm phần tử chung của 3 mảng đã sắp xếp

Tìm giao (intersection) của 3 mảng đã sắp xếp tăng dần bằng kỹ thuật 3 con trỏ (three pointers) — độ phức tạp O(n), chỉ duyệt một lần.

Thuật toán

1. Khởi tạo 3 chỉ số i, j, k = 0 cho 3 mảng.
2. Lặp khi chưa hết mảng nào:
3. Nếu arr1[i] == arr2[j] == arr3[k] → phần tử chung, in ra, tăng cả 3.
4. Nếu arr1[i] < arr2[j] → tăng i.
5. Nếu arr2[j] < arr3[k] → tăng j.
6. Ngược lại → tăng k.

Mã nguồn

using System;

class Demo {
    static void CommonElements(int[] one, int[] two, int[] three) {
        int i = 0, j = 0, k = 0;
        
        while (i < one.Length && j < two.Length && k < three.Length) {
            if (one[i] == two[j] && two[j] == three[k]) {
                Console.Write(one[i] + " ");
                i++; j++; k++;
            } else if (one[i] < two[j]) {
                i++;
            } else if (two[j] < three[k]) {
                j++;
            } else {
                k++;
            }
        }
    }
    
    public static void Main() {
        int[] one = { 20, 35, 57, 70 };
        int[] two = { 9, 35, 57, 70, 92 };
        int[] three = { 25, 35, 55, 57, 67, 70 };
        
        Console.Write("Phần tử chung: ");
        CommonElements(one, two, three);
    }
}

Kết quả

Phần tử chung: 35 57 70

Giải thích

• 3 mảng đều đã sắp xếp → có thể loại bỏ phần tử nhỏ hơn mà không lo bỏ sót phần tử chung.
• Mỗi bước loại bỏ ít nhất 1 phần tử → tối đa n1 + n2 + n3 bước.
• Không dùng HashSet — tiết kiệm bộ nhớ, tận dụng tính đã sắp xếp.

Trường hợp mảng CHƯA sắp xếp

// Dùng HashSet - O(n) thời gian, O(n) bộ nhớ
var set1 = new HashSet(arr1);
var set2 = new HashSet(arr2);
var common = set1.Intersect(set2).Intersect(arr3);

Lưu ý

• Yêu cầu đầu vào: 3 mảng đã sắp xếp.
• Nếu mảng có phần tử trùng lặp, thuật toán trên sẽ in trùng. Cần kiểm tra thêm nếu muốn distinct.
• Mở rộng cho N mảng: dùng min-heap hoặc đếm tần suất (frequency map).