Chương trình đếm số phần tử trong A nhỏ hơn chặt ít nhất k phần tử trong B trong Python

Mô tả bài toán

Cho hai danh sách A, B và số k. Đếm số phần tử trong A mà nhỏ hơn chặt ít nhất k phần tử trong B.

Ví dụ: A = [6, -2, 100, 11], B = [33, 6, 30, 8, 14], k = 3 → đầu ra 3 (-2, 6, 11 đều < 3 phần tử trong B).

Giải thuật (Sắp xếp B giảm dần)

1. Nếu k == 0: trả về len(A).
2. Sắp xếp B giảm dần.
3. Phần tử thứ k lớn nhất trong B là B[k-1].
4. Đếm số phần tử trong A nhỏ hơn B[k-1].

Ví dụ mã Python

class Solution:
    def solve(self, A, B, k):
        if k == 0:
            return len(A)
        B.sort(reverse=True)
        ct = 0
        for i in A:
            if i < B[k - 1]:
                ct += 1
        return ct

ob = Solution()
A = [6, -2, 100, 11]
B = [33, 6, 30, 8, 14]
k = 3
print(ob.solve(A, B, k))

Đầu vào

[6, -2, 100, 11], [33, 6, 30, 8, 14], 3

Đầu ra

3