[DailyCoding] K Max-Min

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.

• Các phần tử trong mảng có trùng nhau hay không?

• Có số thực không?

• Giới hạn về độ lớn của số?

• Kết quả trả về có cần được sắp xếp hay không?

• Trường hợp đặc biệt nếu mảng có số phần tử < 6 thì sao?

• Mở rộng bài toán là tìm x phần tử lớn nhất và x phần tử nhỏ nhất?

Okay mình sẽ trả lời như sau:

• Các phần tử trong mảng không trùng

• Tất cả đều là số nguyên

• Số nguyên 2byte có độ lớn -32768 => 32767

• Kết quả trả về phải được sắp xếp theo thứ tự tăng dần.

• Một mảng các kí tự không trùng > 6

• Yes, bài toán có thể được mở rộng.

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.

Lời giải

def heapify(unsorted, index, heap_size):
    largestIdx = index
    leftIdx = 2*index+1
    rightIdx= 2*index+2
    count +=1
    if leftIdx < heap_size and unsorted[largestIdx]<unsorted[leftIdx]:
        largestIdx=leftIdx
    if rightIdx < heap_size and unsorted[largestIdx]<unsorted[rightIdx]:
        largestIdx=rightIdx
    if largestIdx != index:
        unsorted[largestIdx],unsorted[index] = unsorted[index],unsorted[largestIdx]
        heapify(unsorted,largestIdx,heap_size)

Optimize chỗ tìm phẩn tử max bằng cách sử dụng max_heap + min_heap. Lúc này chi phí để tìm kiếm phần tử max sẽ là log(n) => trong phạm vi bài toán tổng chi phí để tìm k MinMax với heap là : O(k*log(n))