Majority Element

Q: Nếu mảng có thể không có phần tử chiếm đa số thì sao?

Boyer-Moore luôn trả về một ứng viên: với [1, 2, 3] , thuật toán trả về 3. Hãy thêm lượt duyệt thứ hai để đếm số lần xuất hiện của ứng viên và chỉ chấp nhận ứng viên đó nếu số lần xuất hiện lớn hơn n / 2 . Tổng độ phức tạp vẫn là O(n) về thời gian và O(1) về bộ nhớ.

DễBăm

+10

Bạn nhận được một mảng số nguyên nums có độ dài n. Một giá trị xuất hiện trong mảng nhiều hơn n / 2 lần và được gọi là phần tử đa số. Hãy trả về giá trị đó. Giá trị xuất hiện trong hơn một nửa số phần tử của mảng luôn là duy nhất, vì vậy chỉ có một đáp án.

Hàm

majorityElement(nums: integer-array) → integer

numsinteger-array: mảng số nguyên, trong đó một giá trị chiếm hơn một nửa mảng
Trả vềinteger: giá trị xuất hiện nhiều hơn n / 2 lần

Ràng buộc

1 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹
Một giá trị xuất hiện nhiều hơn nums.length / 2 lần.

Ví dụ

Đầu vào: nums = [3, 9, 3, 3, 4]
Đầu ra: 3
Giải thích: Số 3 xuất hiện ba lần trong năm phần tử. Ba lớn hơn 5 / 2 = 2.5, còn 9 và 4 mỗi số xuất hiện một lần.

Câu hỏi mở rộng

Bạn có thể tìm mọi giá trị xuất hiện nhiều hơn n / 3 lần trong thời gian O(n) với bộ nhớ bổ sung O(1) không?

Lời giải

Giá trị chiếm đa số có số lượng lớn hơn tổng số lượng của tất cả các giá trị khác cộng lại. Khi gạch bỏ từng cặp giá trị khác nhau, một số bản sao của nó luôn còn lại. Thuật toán biểu quyết Boyer-Moore ghép các cặp đó trong một lượt duyệt, chỉ cần một ứng viên và một bộ đếm, nên bạn không cần bảng băm để đếm.

Đếm bằng bản đồ băm

Ý tưởng

Đếm số lần xuất hiện của từng giá trị trong bảng băm rồi trả về giá trị đầu tiên có số lần xuất hiện vượt quá một nửa độ dài. Với [3, 9, 3, 3, 4], số lần xuất hiện của 3 đạt 3 tại chỉ số 3, nhiều hơn 2.5, nên bạn trả về giá trị đó trước khi đọc số 4.

Trung bình, mỗi lần tra cứu có độ phức tạp O(1), nên độ phức tạp thời gian là O(n), nhưng bảng có thể chứa khoảng n / 2 giá trị khác nhau: độ phức tạp bộ nhớ là O(n).

Thuật toán

Tạo một map rỗng để lưu giá trị và số lần xuất hiện.
Với mỗi phần tử x, tăng số lần xuất hiện của x thêm 1.
Nếu số lần xuất hiện đó nhân với 2 lớn hơn độ dài của mảng, hãy trả về x.

def majorityElement(nums):
    counts = {}
    for x in nums:
        counts[x] = counts.get(x, 0) + 1
        if counts[x] * 2 > len(nums):
            return x

Biểu quyết Boyer-Moore

Ý tưởng

Giữ một candidate và một count đếm số phiếu của ứng viên chưa bị hủy. Phần tử bằng ứng viên sẽ cộng thêm một phiếu. Phần tử khác sẽ hủy một phiếu, và cả hai đều rời khỏi cuộc đua. Khi count bằng 0, phần tử tiếp theo trở thành ứng viên.

Mỗi lần hủy loại bỏ hai giá trị khác nhau, nên nhiều nhất chỉ loại bỏ được một bản sao của giá trị chiếm đa số. Nếu giá trị chiếm đa số xuất hiện m lần, thì số phần tử còn lại là n - m, ít hơn m và không thể hủy hết mọi bản sao. Mọi phiếu còn lại ở cuối đều thuộc về ứng viên cuối cùng, và trong số đó có một bản sao của giá trị chiếm đa số.

Với [8, 8, 1, 1, 8, 1, 8], count lần lượt là 1, 2, 1, 0 khi các số 1 hủy cả hai số 8. Số 8 tiếp theo khởi động lại count ở mức 1, số 1 tiếp theo hủy số đó, và số 8 cuối cùng lại trở thành ứng viên. Một lượt duyệt với hai biến có độ phức tạp thời gian O(n) và bộ nhớ O(1).

Thuật toán

Gán candidate bằng phần tử đầu tiên và gán count bằng 0.
Với mỗi phần tử x, nếu count bằng 0, hãy đặt x làm ứng viên.
Nếu x bằng ứng viên, hãy cộng 1 vào count. Nếu không, hãy trừ 1.
Sau phần tử cuối cùng, trả về candidate.

def majorityElement(nums):
    candidate = nums[0]
    count = 0
    for x in nums:
        if count == 0:
            candidate = x  # the old candidate's votes are used up
        if x == candidate:
            count += 1
        else:
            count -= 1  # x and one copy of the candidate cancel out
    return candidate

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

“Nhiều hơn một nửa” là điều kiện nghiêm ngặt. count >= n / 2 chấp nhận 2 bản sao trong số 4 bản sao, nhưng đó không phải là đa số. Hãy so sánh count * 2 > n để tránh sai lệch do làm tròn.
Đọc count cuối cùng như tần suất của phần tử chiếm đa số. Với [8, 8, 1, 1, 8, 1, 8], giá trị cuối cùng là 1, trong khi 8 xuất hiện bốn lần.
Bắt đầu với candidate = nums[0] và count = 1, rồi lặp từ chỉ số 0. Phần tử đầu tiên được tính phiếu hai lần: với [1, 2, 2], giá trị cuối cùng của biến đếm là 0 và bạn trả về 1.

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

Độ phức tạp thời gian và không gian của Phần tử chiếm đa số là bao nhiêu?

Thuật toán biểu quyết Boyer-Moore chạy trong thời gian O(n) và cần O(1) bộ nhớ bổ sung. Đếm bằng bảng băm cũng mất thời gian O(n), nhưng cần O(n) bộ nhớ để lưu số lượng. Sắp xếp trước mất thời gian O(n log n).

Liệu có thể giải bài toán phần tử chiếm đa số bằng cách sắp xếp không?

Đúng vậy. Sau khi sắp xếp, tất cả bản sao của phần tử chiếm đa số nằm trong một khối dài hơn một nửa mảng, và khối như vậy luôn bao phủ vị trí chính giữa. Vì thế, phần tử ở chỉ số n / 2, làm tròn xuống, chính là đáp án, với độ phức tạp thời gian O(n log n).

Nếu mảng có thể không có phần tử chiếm đa số thì sao?

Boyer-Moore luôn trả về một ứng viên: với [1, 2, 3], thuật toán trả về 3. Hãy thêm lượt duyệt thứ hai để đếm số lần xuất hiện của ứng viên và chỉ chấp nhận ứng viên đó nếu số lần xuất hiện lớn hơn n / 2. Tổng độ phức tạp vẫn là O(n) về thời gian và O(1) về bộ nhớ.

def majorityElement(nums):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Đối số

nums = [3, 9, 3, 3, 4]

Đầu ra mong đợi