Làm thế nào để đếm các giá trị khác biệt trong một danh sách trong thời gian tuyến tính?

Question

Tôi có thể nghĩ đến việc phân loại chúng và sau đó đi qua từng phần tử một, nhưng điều này là không quan trọng. Có phương pháp tuyến tính nào để tính các phần tử riêng biệt trong danh sách không?

Answer 1

Cập nhật: - khác biệt so với độc đáo

---

Nếu bạn đang tìm kiếm "độc đáo" giá trị (Như trong nếu bạn nhìn thấy một yếu tố "JASON" nhiều hơn một lần, hơn là không có còn độc đáo và không nên được tính)

Bạn có thể làm điều đó trong thời gian tuyến tính bằng cách sử dụng một HashMap;)

(Các tổng quát/ngôn ngữ-agnostic ý tưởng là Hash table)

Mỗi mục của một HashMap/table Hash là <KEY, VALUE> cặp nơi các phím là duy nhất (nhưng không hạn chế đối với giá trị tương ứng của chúng trong cặp)

Bước 1:

Duyệt qua tất cả các yếu tố trong danh sách một lần: O (n)

• Đối với mỗi yếu tố nhìn thấy trong danh sách, kiểm tra để xem nếu nó là trong HashMap đã O (1), khấu hao
  • Nếu không, hãy thêm nó vào HashMap với giá trị của các phần tử trong danh sách là KEY, và số lần bạn đã nhìn thấy giá trị này cho đến nay là GIÁ TRỊ O (1)
  • Nếu vậy, tăng số lần bạn đã nhìn thấy KEY này cho đến nay O (1)

Bước 2:

Duyệt qua HashMap và đếm KEYS với giá trị bằng chính xác 1 (do đó duy nhất) O (n)

Phân tích:

• Runtime: O (n), khấu hao
• Không gian: O (U), trong đó U là số giá trị khác biệt.

---

Tuy nhiên, nếu bạn đang tìm kiếm "khác biệt" giá trị (Như trong nếu bạn muốn đếm có bao nhiêu khác nhau yếu tố có), sử dụng một HashSet thay vì một HashMap/Hash bảng, và sau đó chỉ cần truy vấn kích thước của HashSet.

Answer 2

Bạn có thể điều chỉnh this extremely cool O(n)-time and O(1)-space in-place algorithm để xóa các mục trùng lặp với nhiệm vụ đếm các giá trị riêng biệt - chỉ cần đếm số giá trị bằng giá trị sentinel trong thẻ O (n) cuối cùng và trừ đi từ kích thước của danh sách.

Answer 3

Thêm mọi phần tử của danh sách vào một số HashSet và sau đó kiểm tra size (cardinality) của HashSet, là số giá trị khác biệt trong danh sách.