Đề bài
Sắp xếp các giá trị theo thứ tự tăng dần. Nếu số lượng giá trị là lẻ, lấy giá trị ở giữa. Nếu là chẵn, lấy trung bình cộng của hai giá trị ở giữa. Bài toán này chỉ chấp nhận danh sách không rỗng.
Cài đặt hàm median_number(numbers).
Đầu vào
numbers: Danh sách các giá trị không rỗng.
Đầu ra
Trả về trung vị dưới dạng một số; kết quả có thể kết thúc bằng .5.
Ràng buộc
1 ≤ độ dài danh sách ≤ 100.000. Mỗi giá trị là một số nguyên trong khoảng từ −1.000.000.000 đến 1.000.000.000.
Ví dụ
Đầu vào:
numbers = [2, 8, 4, 10]
Kết quả mong đợi:
expected = 6.0Đầu vào:
std::vector<long long> numbers = {2, 8, 4, 10};
Kết quả mong đợi:
double expected = 6.0;Đầu vào:
long[] numbers = new long[] {2, 8, 4, 10};
Kết quả mong đợi:
double expected = 6.0;Giải thích
Thứ tự sau khi sắp xếp là 2, 4, 8, 10. Cặp ở giữa có trung bình cộng là (4 + 8) / 2 = 6.
Đầu vào:
numbers = [9, 1, 4]
Kết quả mong đợi:
expected = 4.0Đầu vào:
std::vector<long long> numbers = {9, 1, 4};
Kết quả mong đợi:
double expected = 4.0;Đầu vào:
long[] numbers = new long[] {9, 1, 4};
Kết quả mong đợi:
double expected = 4.0;Giải thích
Thứ tự sau khi sắp xếp là 1, 4, 9, giá trị ở giữa là 4.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Trung vị phụ thuộc vào thứ tự sau khi sắp xếp, nên vị trí trong mảng đã sắp mới là quan trọng.
Gợi ý 2
Sau khi sắp xếp, lấy phần tử giữa nếu độ dài lẻ, hoặc kết hợp hai phần tử giữa nếu độ dài chẵn.
Gợi ý 3
Cẩn thận giữ phần thập phân khi lấy trung bình hai giá trị giữa, vì kết quả có thể là .5.
Độ phức tạp mong đợi
thời gian O(n log n), bộ nhớ phụ O(n)
Tham khảo
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.