K-th Smallest Element

Đề bài

Return the k-th smallest value of the list (k counts from 1). Quickselect finds it in average O(n) time without sorting everything.

Implement kth_smallest(numbers, k).

numbers: The list of integers. k: Which smallest value to return, starting at 1.

Return the k-th smallest value.

1 ≤ k ≤ length ≤ 200,000

Ví dụ 1

Đầu vào:
k = 3
numbers = [7, 10, 4, 3, 20, 15]

Kết quả mong đợi:
expected = 7

Đầu vào:
long long k = 3;
std::vector<long long> numbers = {7, 10, 4, 3, 20, 15};

Kết quả mong đợi:
long long expected = 7;

Đầu vào:
long k = 3;
long[] numbers = new long[] {7, 10, 4, 3, 20, 15};

Kết quả mong đợi:
long expected = 7;

Sorted: 3, 4, 7, 10, 15, 20; the 3rd smallest is 7.

Ví dụ 2

Đầu vào:
k = 2
numbers = [5, 5, 1]

Kết quả mong đợi:
expected = 5

Đầu vào:
long long k = 2;
std::vector<long long> numbers = {5, 5, 1};

Kết quả mong đợi:
long long expected = 5;

Đầu vào:
long k = 2;
long[] numbers = new long[] {5, 5, 1};

Kết quả mong đợi:
long expected = 5;

Sorted: 1, 5, 5; the 2nd smallest is 5 (duplicates count).

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

Bạn chỉ cần phần tử sẽ đứng ở vị trí k sau khi sắp xếp, không cần danh sách đã sort hoàn chỉnh.

Gợi ý 2

Partition quanh một pivot rồi chỉ đệ quy/lặp sang phía còn có thể chứa thứ hạng mục tiêu.

Gợi ý 3

Nhớ rằng k là tính từ 1, và các phần tử trùng nhau vẫn phải được tính là các vị trí riêng.

Độ phức tạp mong đợi

O(n) average time, O(1) extra space

Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.