## 題解

### MinHeap (Priority Queue) <span style="color: red;">Timeout</span>

class Heap:
    def __init__(self):
        self.heap = []

    @property
    def length(self):
        return len(self.heap)

    def insert(self, val: int):
        self.heap.append(val)
        self.swin(self.length - 1)

    def pop(self):
        value = self.heap[0]
        self.swap(0, self.length - 1)
        self.heap.pop()
        self.sink(0)
        return value

    def top(self):
        if self.length > 0:
            return self.heap[0]
        return None

    def parent(self, k):
        return (k - 1) // 2

    def swap(self, m: int, n: int):
        self.heap[m], self.heap[n] = self.heap[n], self.heap[m]


class MaxHeap(Heap):
    def swin(self, k: int):
        while k > 0 and self.heap[self.parent(k)] < self.heap[k]:
            self.swap(self.parent(k), k)
            k = self.parent(k)

    def sink(self, k: int):
        while k * 2 + 1 < self.length:
            left, right = k * 2 + 1, k * 2 + 2
            target = left
            if right < self.length and self.heap[left] < self.heap[right]:
                target = right
            if self.heap[k] >= self.heap[target]:
                break
            self.swap(k, target)
            k = target


class MinHeap(Heap):
    def swin(self, k: int):
        while k > 0 and self.heap[self.parent(k)] > self.heap[k]:
            self.swap(self.parent(k), k)
            k = self.parent(k)

    def sink(self, k: int):
        while k * 2 + 1 < self.length:
            left, right = k * 2 + 1, k * 2 + 2
            target = left
            if right < self.length and self.heap[left] > self.heap[right]:
                target = right
            if self.heap[k] <= self.heap[target]:
                break
            self.swap(k, target)
            k = target


class Solution:
    def findKthNumber(self, m: int, n: int, k: int) -> int:
        # Min_heap
        # Time complexity: O(m*nlogn+k)
        # Space complexity: O(m*n)
        min_heap = MinHeap()
        for i in range(1,m + 1):
            for j in range(1,n + 1):
                num = i * j
                min_heap.insert(num)
        ans = 0
        for i in range(k):
            ans = min_heap.pop()
        return ans

### Binary Search