Mảng với các giá trị cụ thể

Question

Cho một mảng có kích thước n trong đó: 1/2 của mảng là với một giá trị đơn (không xác định). 1/4 của mảng là với một giá trị khác nhau (không xác định) khác nhau. Và cứ như vậy cho 1/8, 1/16, 1/32 Đưa ra thuật toán sắp xếp mảng. Bạn không thể sử dụng tìm thuật toán trung bình

Vì vậy, những gì tôi hình dung là: Chỉ có giá trị logn khác nhau Có một giải pháp đơn giản sử dụng một đống nhị phân trên O (n * loglogn) Nó trông giống như một câu hỏi đó cần thiết để được giải quyết trong thời gian O (n)

Answer 1

Ý tưởng là để sử dụng các thuật toán Đa số mà mất O (n) sau đó phát hiện ra những gì là "một nửa" giá trị xóa nó từ mảng và sau đó làm việc đó một lần nữa trên mảng mới n + n/2 + n/4 + n/8 + ..... < 2n => O (n)

Answer 2

Dưới đây là một cách tiếp cận có thể:

• quét mảng và lưu trữ các tần số nguyên tố (có đăng nhập n phần tử riêng biệt) trong một bảng băm trong amortized O (n) thời gian ; điều này có thể thực hiện được vì we can do insertions in amortized O(1) time;
• hiện đang chạy thuật toán phân loại cổ điển trên các phần tử n nhật ký này: có thể thực hiện được trong thời gian xác định O (nhật ký log log n) bằng cách sử dụng, sắp xếp đống hoặc hợp nhất;
• bây giờ mở rộng mảng đã sắp xếp --- hoặc tạo một mảng mới và điền vào nó bằng cách sử dụng mảng được sắp xếp và bảng băm --- sử dụng tần số từ bảng băm; điều này có thể thực hiện được trong O (n) thời gian khấu hao.

Do đó, toàn bộ thuật toán chạy trong thời gian O (n) được phân bổ, tức là nó bị chi phối bởi loại bỏ các bản sao và mở rộng mảng được sắp xếp. Độ phức tạp của không gian là O (n). Đây là cơ bản tối ưu bởi vì bạn cần phải "chạm" tất cả các yếu tố để in mảng được sắp xếp, có nghĩa là chúng tôi có một ràng buộc thấp hơn phù hợp của Omega (n) vào thời gian chạy.

Answer 3

Đi qua mảng một lần, giữ bản đồ băm cho các giá trị đã xem. Như bạn đã nói chỉ có log(n) giá trị khác nhau.

Bây giờ bạn có danh sách của tất cả các giá trị khác nhau - sắp xếp họ sẽ mất lon(n)*log(log(n))

Khi bạn có uniq được sắp xếp như thật dễ dàng để constract mảng ban đầu: Giá trị tối đa sẽ mất n/2 tế bào, thứ 2 mất n/4 và vân vân.

Các Tổng thời gian chạy là O(n + lon(n)*log(log(n)) + n) đó là O(n)