Câu hỏi

Cho 1 tỷ số thực, tìm 1 triệu số nhỏ nhất trong 1 tỷ số đấy.

Phân tích

Cách giải đơn giản nhất là sắp xếp từ bé đến lớn 1 tỷ số đầu vào, sau đó chọn ra 1 triệu số đầu tiên. Độ phức tạp của cách giải này phụ thuộc vào độ phức tạp của thuật toán sắp xếp. Cách này có hai nhược điểm lớn: 1. là tốn bộ nhớ để chứa 1 tỷ số đầu vào để sắp xếp, 2. là nếu số lượng đầu vào không có giới hạn thì cách giải này không dùng được.

Giả sử ta chỉ có 1 triệu số đầu vào, thì rõ ràng kết quả sẽ chính là 1 triệu số đó. Khi có thêm 1 số mới, số mới này sẽ nằm trong kết quả nếu như nó nhỏ hơn số lớn nhất trong 1 triệu số kết quả hiện tại.

Với nhận xét đó, ta có cách giải thứ hai, tối ưu hơn cách đầu tiên. Ta sẽ tạo một max heap với 1 triệu phần tử. Với mỗi phần tử đầu vào, ta sẽ:

1. Đưa vào heap nếu heap chưa có đủ 1 triệu số
2. Nếu heap đã có đủ một triệu số thì lấy từ đỉnh heap ra (tức lấy phần tử lớn nhất trong heap) so sánh với phần tử đầu vào, và đưa lại vào heap phần tử nhỏ hơn trong phép so sánh đó.

Độ phức tạp thực thi của cách giải này là O(nlogn) nhưng chỉ tốn bộ nhớ tỷ lệ với số phần tử đầu ra.

Cài đặt

Ta có thể dùng mô-đun heapq có sẵn để trả lời câu hỏi này. Mô-đun này giúp ta quản lý một min heap. Tuy nhiên, vì ta cần max heap nên các giá trị đầu vào sẽ được đổi thành số bù 0 - x.

# encoding: utf-8
import heapq

def solve(inp, n=1000000):
    heap = []
    for i in inp:
        i = -i
        if len(heap) < n:
            heapq.heappush(heap, i)
        else:
            m = heap[0]
            if m < i:
                heapq.heapreplace(heap, i)
    return [-x for x in heap]

assert(set(solve([1, 2, 3, 4, 5], 3)) == set([1, 2, 3]))
assert(set(solve([5, 4, 3, 2, 1], 3)) == set([1, 2, 3]))

Mô-đun heapq cũng có sẵn hàm nsmallest để giải quyết câu hỏi này ;).