Status: Resolved
Cho một mảng các phần tử a, tìm ra 3 số nhỏ nhất và 3 số lớn nhất trong dãy.
Ví dụ mảng a=[ 5, 6, 1, 88, -1, 19, 8, -7, 27] => kết quả là: [ -7, -1, 1, 19, 27, 88]
Hm.... khoan hãy làm nha, cùng phân tích trước khi giải xem nào.
Okay mình sẽ trả lời như sau:
Sau khi nắm đầy đủ thông tin thì bắt đầu code thôi. Khi tiếp cận bài toán này phương pháp đầu tiên mình nghĩ ra đó là Sort sau đó lấy 3 kí tự đầu và 3 kí tự cuối.
Có thể giải quyết được bài toán, nhưng vấn đề là Sort kiểu thông thường thì có độ phức tạp lớn O(n*n). Mình sẽ thử optimize bằng MergeSort hay QuickSort có độ phức tạp trung bình là O(n*logn).
Hm... sao ta...Sort cũng được nhưng mà mình cảm giác vẫn có thể làm tốt hơn được ở đây. Nếu mà tìm 3 phần tử lớn nhất hay nhỏ nhất, như vậy thì sort cái mảng sao cho ra được 3 phần tử lớn với 3 phần tử nhỏ nhất mình stop luôn nhỉ. Đỡ phải tốn thời gian Sort toàn bộ mảng.
Nếu mà theo hướng này chắc mình sẽ implement BubbleSort. Sau mỗi vòng lặp thì BubbleSort sẽ sắp xếp được một phần tử lớn nhất hoặc nhỏ nhất. Như vậy chỉ cần sort 6 lần? Lúc này độ phức tạp O(6*n).
Một số bạn đưa ra idea sử dụng max-heap để optimize thời gian sort.
Any idea?
TIME TO CODE. Các bạn cùng giải với mình, nếu có lời giải hay thì share mình với nha.
Lời giải của mình: