Đề bài
Một giáo viên nhập điểm kiểm tra vào chương trình và kết thúc danh sách bằng một số âm bất kỳ. Số âm này chỉ là tín hiệu dừng (giá trị lính canh, sentinel), không phải là điểm. Chương trình cần cho biết điểm nằm ở giữa theo đúng thứ tự đã nhập (các điểm không được sắp xếp). Với k điểm, điểm ở giữa nằm ở vị trí k / 2 (đánh số từ 0, làm tròn xuống), nên khi số lượng là chẵn thì đó là điểm thứ hai trong hai điểm ở giữa.
Hãy viết middle_item(values).
Đầu vào
values: Các số theo thứ tự nhập. Việc đọc dừng ở số âm đầu tiên; số đó và mọi số phía sau đều bị bỏ qua. Nếu không có số âm nào thì mọi giá trị đều là điểm.
Đầu ra
Trả về điểm ở giữa. Nếu không có điểm nào trước tín hiệu dừng, trả về -1.
Ràng buộc
0 ≤ độ dài values ≤ 1000
−1000 ≤ mỗi giá trị ≤ 1000
Ví dụ
Đầu vào:
values = [88, 72, 95, 60, 81, -1]
Kết quả mong đợi:
expected = 95
Đầu vào:
std::vector<long long> values = {88, 72, 95, 60, 81, -1};
Kết quả mong đợi:
long long expected = 95;
Đầu vào:
long[] values = new long[] {88, 72, 95, 60, 81, -1};
Kết quả mong đợi:
long expected = 95;
Giải thích
Các điểm là 88, 72, 95, 60, 81; có 5 điểm nên phần tử giữa ở vị trí 2, tức là 95.
Đầu vào:
values = [10, 20, 30, 40, -5, 50]
Kết quả mong đợi:
expected = 30
Đầu vào:
std::vector<long long> values = {10, 20, 30, 40, -5, 50};
Kết quả mong đợi:
long long expected = 30;
Đầu vào:
long[] values = new long[] {10, 20, 30, 40, -5, 50};
Kết quả mong đợi:
long expected = 30;
Giải thích
Việc đọc dừng ở −5, còn lại 4 điểm; vị trí 2 là 30.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Chép các giá trị sang một danh sách mới cho đến khi gặp số âm đầu tiên.
Gợi ý 2
Với k phần tử, chỉ số ở giữa là k / 2 (chia lấy phần nguyên).
Gợi ý 3
Nếu không chép được phần tử nào thì không có phần tử ở giữa.
Độ phức tạp mong đợi
thời gian O(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.