để tìm ba phần tử chính trong một mảng

Question

Giả sử có ba phần tử trong một mảng không được sắp xếp tất cả đều xuất hiện nhiều hơn một phần tư tổng số phần tử.

Cách hiệu quả nhất để tìm các yếu tố này là gì? Cả hai phiên bản không trực tuyến và trực tuyến của câu hỏi này.

Cảm ơn bạn!

Sửa

Phiên bản phi trực tuyến Tôi đã đề cập đến là: mảng này được quy định đầy đủ. Phiên bản trực tuyến có nghĩa là các phần tử mảng đang đến một tại một thời điểm.

Tôi yêu cầu không gian ngoài độ phức tạp của thời gian.

tuyên bố từ chối trách nhiệm: ĐÂY KHÔNG PHẢI LÀ GÌ! Tôi coi đây là câu hỏi cấp độ nghiên cứu.

Answer 1

tạo biểu đồ các mục nhập, sắp xếp và lấy ba mục nhập lớn nhất.

Answer 2

Hãy nhớ tối đa ba yếu tố, cùng với bộ đếm.

1. nhớ yếu tố đầu tiên, thiết lập count1 = 1
2. quét cho đến khi bạn tìm thấy phần tử đầu tiên khác nhau, tăng count1 cho mỗi lần xuất hiện của yếu tố 1
3. nhớ elemt thứ hai, thiết lập count2 = 1
4. quét cho đến khi bạn tìm phần tử đầu tiên khác với elem1 và elem2, tăng số đếm1 hoặc đếm2, tùy thuộc vào yếu tố nào bạn nhìn thấy
5. nhớ phần tử thứ ba, đặt count3 = 1
6. tiếp tục quét, nếu phần tử là một phần của bản ghi nhớ ered, tăng số lượng của nó, nếu đó là không ai trong số nhớ, giảm cả ba đếm; nếu số lượng giảm xuống 0, hãy quên phần tử, chuyển đến bước 1, 3 hoặc 5, tùy thuộc vào số phần tử bạn quên
7. Nếu bạn có ba phần tử xuất hiện nhiều hơn một phần tư số lượng phần tử trong mảng, bạn sẽ kết thúc với ba yếu tố được nhớ với mỗi yếu tố tích cực, đây là ba yếu tố đa số.

Không gian bổ sung không đổi nhỏ, O (n), không phân loại.