Thuật toán nào được sử dụng để tìm mảng con thứ n được sắp xếp của một mảng không có thứ tự?

Question

Tôi đã có câu hỏi này gần đây trong một cuộc phỏng vấn và tôi đã thất bại, và bây giờ tìm kiếm câu trả lời.

1. Giả sử tôi có một mảng lớn gồm n số nguyên, tất cả đều khác nhau.

2. Nếu mảng này được đặt hàng, tôi có thể chia nhỏ mảng này thành x nhỏ hơn mảng, tất cả kích thước y, ngoại trừ số cuối cùng, có thể ít hơn. Tôi có thể trích xuất phần con thứ n và trả về nó, đã được sắp xếp.

Ví dụ: Mảng 4 2 5 1 6 3. Nếu y = 2 và tôi muốn các mảng thứ 2, nó sẽ là 3 4.

Bây giờ những gì tôi đã chỉ đơn giản là sắp xếp mảng và trả lại sub subarray, trong đó có O (n log n). Nhưng nó đã được nói với tôi rằng có tồn tại một cách để làm điều đó trong O(n + y log y). Tôi đã tìm kiếm trên internet và không tìm thấy gì cả. Ý tưởng?

Answer 1

Thuật toán bạn đang tìm kiếm là Selection Algorithm, cho phép bạn tìm thấy k-th order statistics trong thời gian tuyến tính. Thuật toán khá phức tạp, nhưng thư viện chuẩn C++ thuận tiện cung cấp an implementation của nó.

Thuật toán cho việc tìm kiếm thứ k khoảng sắp xếp mà người phỏng vấn đã có trong tâm trí đi như thế này:

• Tìm b=(k-1)*y thống kê theo thứ tự -thứ trong thời gian O (N)
• Tìm e=k*y thống kê theo thứ tự -thứ trong O (N)
• Sẽ có y số giữa b và e. Lưu trữ chúng trong một mảng riêng biệt có kích thước y. Thao tác này mất O (N)
• Sắp xếp mảng có kích thước y cho chi phí O (y * log y).

Chi phí tổng thể là O (N + N + N + y * log y), tức là O (N + y * log y)

Answer 2

Bạn có thể kết hợp std::nth_element và std::sort cho điều này:

std::vector<int> vec = muchData(); 
// Fix those bound iterators as needed 
auto lower = vec.begin() + k*y; 
auto upper = lower + y; 

// put right element at lower and partition vector by it 
std::nth_element(vec.begin(), lower, vec.end()); 
// Same for upper, but don't mess up lower 
std::nth_element(lower + 1, upper - 1, vec.end()); 
// Now sort the subarray 
std::sort(lower, upper); 

[lower, upper) bây giờ là phân đoạn thứ k được sắp xếp theo chiều dài y, với độ phức tạp mong muốn.

Để được kiểm tra các trường hợp đặc biệt như y = 1 trước khi sử dụng thực tế, nhưng đây là ý tưởng chung.