Tìm số N-thứ thường gặp nhất trong mảng

Question

Find the nth most frequent number in array. 
(There is no limit on the range of the numbers) 

Tôi nghĩ rằng chúng ta có thể

(i) lưu trữ sự xuất hiện của tất cả các yếu tố sử dụng bản đồ trong C++

(ii) xây dựng một Max-đống trong thời gian tuyến tính của các lần xuất hiện (hoặc tần số) của phần tử và sau đó trích xuất tối đa phần tử thứ N, Mỗi lần khai thác mất thời gian log (n) để heapify.

(iii), chúng tôi sẽ nhận được tần số của N-thứ số thường gặp nhất

(iv) sau đó chúng ta có thể tuyến tính tìm kiếm thông qua các băm để tìm các phần tử có tần số này.

Time - O (NlogN) Space - O (N)

Có phương pháp nào tốt hơn?

Answer 1

Phương pháp của bạn về cơ bản là đúng. Bạn sẽ tránh tìm kiếm băm cuối cùng nếu bạn đánh dấu từng đỉnh của đống được xây dựng với số mà nó đại diện. Hơn nữa, có thể liên tục theo dõi yếu tố thứ năm của đống khi bạn đang xây dựng nó, bởi vì tại một thời điểm nào đó bạn có thể tới một tình huống mà kết quả không thể thay đổi được nữa và phần còn lại của phép tính có thể bị loại bỏ. Nhưng điều này có lẽ sẽ không làm cho thuật toán nhanh hơn trong trường hợp chung, và có thể thậm chí không trong trường hợp đặc biệt. Vì vậy, bạn trả lời câu hỏi của riêng bạn một cách chính xác.

Answer 2

Tùy thuộc vào việc bạn muốn phương pháp hiệu quả nhất hay dễ nhất để viết.

1) nếu bạn biết rằng tất cả các số sẽ từ 0 đến 1000, bạn chỉ cần tạo một mảng 1000 số không (lần xuất hiện), lặp qua mảng của bạn và tăng vị trí đúng. Sau đó, bạn sắp xếp các lần xuất hiện này và chọn giá trị Nth.

2) Bạn có một "túi" các mặt hàng độc đáo, bạn lặp qua các số của mình, kiểm tra xem số đó có nằm trong túi hay không, nếu bạn thêm số đó, nếu nó ở đây, bạn chỉ cần tăng số lần xuất hiện . Sau đó, bạn chọn một số nhỏ nhất Nth từ nó.

Túi có thể là mảng tuyến tính, BST hoặc Từ điển (bảng băm).

Câu hỏi đặt ra là "N-thứ thường xuyên nhất", vì vậy tôi nghĩ rằng bạn không thể tránh sắp xếp (hoặc cấu trúc dữ liệu thông minh), vì vậy tốt nhất phức tạp không thể là tốt hơn so với O (n * log (n)).

Answer 3

Có thể thực hiện trong thời gian và không gian tuyến tính. Gọi T là tổng số phần tử trong mảng đầu vào mà từ đó chúng tôi phải tìm số thứ N thường xuyên nhất:

1. Đếm và lưu tần số của mỗi số trong T trong bản đồ. Gọi M là tổng số phần tử riêng biệt trong mảng. Vì vậy, kích thước của bản đồ là M. - O (T)
2. Tìm tần số lớn nhất thứ N trong bản đồ bằng cách sử dụng Selection algorithm. - O (M)

Tổng thời gian = O (T) + O (M) = O (T)