Intersection of Two Arrays

Q: Độ phức tạp thời gian của phép giao hai mảng là gì?

Với tập hợp băm, việc tìm các giá trị chung mất O(n + m) trung bình, cộng thêm O(k log k) để sắp xếp kết quả và cần O(n) không gian. Sắp xếp cả hai mảng rồi duyệt qua chúng mất O(n log n + m log m) . So sánh từng cặp mất O(n × m) .

DễBăm

+10

Bạn nhận được hai mảng số nguyên nums1 và nums2. Hãy trả về mọi giá trị xuất hiện trong cả hai mảng, được sắp xếp theo thứ tự tăng dần. Mỗi giá trị chung chỉ xuất hiện một lần trong đáp án, dù nó lặp lại bao nhiêu lần trong mỗi mảng.

Hàm

intersection(nums1: integer-array, nums2: integer-array) → integer-array

nums1integer-array: danh sách số nguyên đầu tiên
nums2integer-array: danh sách số nguyên thứ hai
Trả vềinteger-array: các giá trị có trong cả hai danh sách, mỗi giá trị một lần, theo thứ tự tăng dần

Ràng buộc

1 ≤ nums1.length, nums2.length ≤ 5000
-10⁵ ≤ nums1[i], nums2[i] ≤ 10⁵
Có ít nhất một giá trị xuất hiện trong cả hai mảng.

Ví dụ

Đầu vào: nums1 = [6, 2, 9, 2, 4]nums2 = [4, 4, 1, 6]
Đầu ra: [4, 6]
Giải thích: 4 và 6 đều có trong cả hai mảng. 4 xuất hiện hai lần trong nums2 nhưng chỉ được liệt kê một lần, còn 2 và 9 không xuất hiện trong nums2.

Đầu vào: nums1 = [-3, 0, 7]nums2 = [7, -3, -3, 5]
Đầu ra: [-3, 7]
Giải thích: -3 và 7 đều có trong cả hai mảng. Theo thứ tự tăng dần, -3 đứng trước, dù 7 đứng trước trong nums2.

Câu hỏi mở rộng

Nếu nums1 chứa 10 giá trị còn nums2 chứa một triệu giá trị và đã được sắp xếp thì sao? Bạn sẽ chọn cách nào, và tìm kiếm nhị phân có thể nhanh hơn việc duyệt toàn bộ không?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Mỗi giá trị chung chỉ xuất hiện một lần trong đáp án, dù nó lặp lại bao nhiêu lần, và đáp án phải được sắp xếp. Sắp xếp cả hai mảng giúp hai con trỏ lần lượt gặp các giá trị chung, còn tập hợp băm của một mảng cho phép kiểm tra “giá trị này có trong nums1 không?” trong thời gian hằng số.

So sánh từng cặp

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Với mỗi giá trị trong nums1, hãy duyệt nums2 và dừng ở lần khớp đầu tiên. Bỏ qua giá trị đã có trong đáp án, vì vậy [8, 8, 8, 8] so với [8, 8] sẽ cho ra một 8, rồi sắp xếp đáp án ở cuối. Một giá trị chỉ được thêm vào khi có ít nhất một bản sao của nó tìm được kết quả khớp, và bước bỏ qua giúp giá trị đó chỉ xuất hiện một lần. Mỗi giá trị có thể phải duyệt toàn bộ nums2: với 5000 giá trị trong mỗi mảng, số phép so sánh có thể lên đến 2.5 × 10^7, và khi chỉ có ít giá trị khớp, hầu hết các lần duyệt đều chạy đến cuối.

Thuật toán

Bắt đầu với một danh sách kết quả rỗng.
Với mỗi giá trị a trong nums1, bỏ qua giá trị đó nếu nó đã có trong danh sách kết quả.
Nếu không, hãy duyệt nums2; khi gặp giá trị đầu tiên bằng a, thêm a vào danh sách kết quả rồi dừng duyệt.
Sắp xếp danh sách kết quả theo thứ tự tăng dần rồi trả về danh sách đó.

def intersection(nums1, nums2):
    result = []
    for a in nums1:
        if a in result:
            continue
        # Look for a anywhere in nums2.
        for b in nums2:
            if a == b:
                result.append(a)
                break
    result.sort()
    return result

Sắp xếp cả hai, rồi duyệt bằng hai con trỏ

Ý tưởng

Sau khi sắp xếp, ví dụ 1 trở thành [2, 2, 4, 6, 9] và [1, 4, 4, 6]. Di chuyển con trỏ ở giá trị nhỏ hơn: giá trị đó không thể khớp với bất kỳ giá trị nào ở phía sau trong mảng còn lại, vì mọi giá trị ở đó đều lớn hơn hoặc bằng nó. Các giá trị bằng nhau xuất hiện trong cả hai mảng, vì vậy hãy thêm giá trị đó và di chuyển cả hai con trỏ. Một giá trị lặp lại ở cả hai bên, như 2 trong [2, 2, 3] và [2, 2], sẽ khớp hai lần; so sánh với giá trị cuối cùng đã thêm để chỉ giữ lại một bản sao. Kết quả được sắp xếp.

Việc sắp xếp có độ phức tạp O(n log n + m log m), còn quá trình duyệt có độ phức tạp O(n + m), vì mỗi bước đều di chuyển một con trỏ. Việc sắp xếp các bản sao cần O(n + m) bộ nhớ; sắp xếp tại chỗ như code C thực hiện chỉ để lại kết quả.

Thuật toán

Sắp xếp cả hai mảng.
Đặt i = 0 và j = 0.
Khi cả hai con trỏ vẫn nằm trong mảng của chúng, di chuyển con trỏ trỏ đến giá trị nhỏ hơn.
Nếu hai giá trị bằng nhau, thêm giá trị đó trừ khi nó bằng giá trị cuối cùng đã thêm, rồi di chuyển cả hai con trỏ.
Trả về đáp án.

def intersection(nums1, nums2):
    a = sorted(nums1)
    b = sorted(nums2)
    i, j = 0, 0
    result = []
    while i < len(a) and j < len(b):
        if a[i] < b[j]:
            i += 1
        elif a[i] > b[j]:
            j += 1
        else:
            # A shared value: keep it once, even if it repeats.
            if not result or result[-1] != a[i]:
                result.append(a[i])
            i += 1
            j += 1
    return result

Tập hợp băm của mảng thứ nhất

Ý tưởng

Đưa mọi giá trị trong nums1 vào một tập hợp băm; trong ví dụ 1, giá trị 2 lặp lại sẽ gộp thành một, còn lại {6, 2, 9, 4}. Duyệt nums2 và tra cứu từng giá trị trong thời gian hằng số, xóa giá trị khỏi tập hợp ngay khi tìm thấy giá trị khớp: giá trị 4 đầu tiên được đưa vào kết quả, còn lần xuất hiện thứ hai không tìm thấy gì. Mọi giá trị được thêm vào đều có trong cả hai mảng, và mọi giá trị chung đều được thêm vào ở lần xuất hiện đầu tiên trong nums2.

Trung bình, việc duyệt mất O(n + m). Kết quả giữ nguyên thứ tự của nums2, vì vậy hãy sắp xếp k ≤ min(n, m) giá trị của nó trong O(k log k). C không có sẵn tập hợp, nên code C dùng một mảng cờ được đánh chỉ số bằng value + 10^5.

Thuật toán

Tạo một tập hợp băm first từ nums1.
Với mỗi giá trị trong nums2, nếu giá trị đó có trong first, hãy thêm nó vào đáp án rồi xóa nó khỏi first.
Sắp xếp đáp án theo thứ tự tăng dần.
Trả về đáp án.

def intersection(nums1, nums2):
    first = set(nums1)
    result = []
    for num in nums2:
        if num in first:
            result.append(num)
            # Remove it so a repeat in nums2 is not added twice.
            first.remove(num)
    result.sort()
    return result

Lỗi thường gặp và trường hợp biên

Cộng một giá trị mỗi khi giá trị đó trùng khớp. [2, 2, 3, 3, 3] và [3, 2, 2] cho ra [2, 3], không phải [3, 2, 2].
Trả về các giá trị theo thứ tự tìm thấy. Duyệt qua tập hợp băm theo nums2, nên phải sắp xếp [7, -3] thành [-3, 7]. set(nums1) & set(nums2) trong Python cũng cần sorted.
Sắp xếp số dưới dạng văn bản. sort() trong JavaScript không có hàm so sánh sẽ giữ nguyên thứ tự [100000, 99]. Hãy truyền (x, y) => x - y.
Dùng giá trị thô làm chỉ số cho mảng cờ. -3 không phải chỉ số hợp lệ; hãy cộng 10^5 vào mỗi giá trị.

Câu hỏi thường gặp3

Độ phức tạp thời gian của phép giao hai mảng là gì?

Với tập hợp băm, việc tìm các giá trị chung mất O(n + m) trung bình, cộng thêm O(k log k) để sắp xếp kết quả và cần O(n) không gian. Sắp xếp cả hai mảng rồi duyệt qua chúng mất O(n log n + m log m). So sánh từng cặp mất O(n × m).

Bạn nên dùng tập hợp băm hay hai con trỏ?

Dùng tập hợp băm (hash set) khi các mảng (array) chưa được sắp xếp và còn bộ nhớ: cách này tốn ít công sức nhất. Dùng hai con trỏ (two pointers) khi cả hai mảng đã được sắp xếp, hoặc khi bộ nhớ hạn chế và bạn có thể sắp xếp chúng ngay tại chỗ. Quá trình duyệt không cần tập hợp và tạo ra kết quả theo đúng thứ tự.

Làm thế nào để giữ lại các giá trị lặp lại trong phần giao?

Khi một giá trị cần xuất hiện nhiều lần như số lần nó có mặt trong cả hai mảng, chẳng hạn [3, 1, 3, 3] và [3, 3] cho kết quả [3, 3], hãy đếm các giá trị trong nums1 bằng một map. Với mỗi giá trị trong nums2 có số lần xuất hiện lớn hơn 0, hãy thêm giá trị đó rồi giảm số lần xuất hiện. Cách duyệt bằng hai con trỏ chỉ bỏ bước kiểm tra giá trị cuối cùng được thêm vào.

def intersection(nums1, nums2):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Đối số

nums1 = [6, 2, 9, 2, 4]
nums2 = [4, 4, 1, 6]

Đầu ra mong đợi

[4, 6]

Intersection of Two Arrays

Hàm

Ràng buộc

Ví dụ

Gợi ý

Lời giải

So sánh từng cặp

Sắp xếp cả hai, rồi duyệt bằng hai con trỏ

Tập hợp băm của mảng thứ nhất

Lỗi thường gặp và trường hợp biên

Câu hỏi thường gặp3

Bài tập tương tự