Mô phỏng thuật toán Phần tử nhỏ thứ k

K-th Order Statistic · Nhóm: Mảng

Phần tử nhỏ thứ k (K-th Order Statistic), nhóm Mảng.

Mã Python

def kth_smallest(a, k):
    target = k - 1
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        pivot = a[hi]
        i = lo
        for j in range(lo, hi):
            if a[j] < pivot:
                a[i], a[j] = a[j], a[i]
                i += 1
        a[i], a[hi] = a[hi], a[i]
        if i == target:
            return a[i]
        lo = i + 1   # pivot too small: go right
        hi = i - 1   # pivot too large: go left

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.