01/10/2018, 11:35
Tìm số lớn thứ 3 trong dãy 5 số mà không dùng quá 6 phép so sánh
Câu hỏi như đề bài. Em có ý tưởng như này (lấy ý tưởng từ quick sort) nhưng chắc sai:
Chọn số đầu tiên lưu vào một biến;
Lần lược sắp xếp các phần tử về 2 phía của phần tử mình chọn;
Xem thứ tự của số mình chọn ban đầu, nếu không phải phần tử thứ ba thì xét về 1 phía mình vừa phân ra
Lặp lại các bước trên cho đến khi tìm được phần tử lớn thứ 3
Vấn đề là nếu dãy đã sắp xếp rồi thì số phép so sánh là 4+3+2=9 phép, loại.
Có cao nhân nào giúp đỡ em về phần ý tưởng được không? Em mới là sinh viên năm nhất mà đã gặp bài hack não rồi.
Bài liên quan
Lại nhớ đến challenge hôm nọ của mình =))
Thuật của bạn giống chia để trị hơn đấy.
Được dùng hàm cho sẵn không thế nhỉ? Mà nếu được dùng STL thì dùng STL map cho nhanh chứ ngồi so sánh làm gì cho mất công.
Tham khảo Quickselect. Hàm chia đôi kinh điển [sic] chậm hơn hẳn so với hàm tiến vào từ cả hai đầu.