Chương trình tìm dãy con phần tử nhỏ nhất theo từ điển (lexicographically smallest subsequence) kích thước k trong Python

Cho danh sách số nums và số nguyên k. Tìm dãy con (subsequence) kích thước k có thứ tự từ điển nhỏ nhất.

Ví dụ: nums = [2, 3, 1, 10, 3, 4], k=3 → kết quả [1, 3, 4].

Giải thuật (Tham lam với chỉ số ngược)

Sử dụng chỉ số ngược (~i) để duyệt từ phải sang trái, chọn phần tử nhỏ nhất có thể trong phạm vi cho phép.

• Khởi tạo l = len(nums), r = k-1, danh sách kết quả out.
• Lặp k lần:
  • mn = nums[~r] (phần tử tại chỉ số len-1-r).
  • Duyệt i từ r đến l-1 (theo chỉ số ngược): nếu mn >= nums[~i], cập nhật mn và l = i.
  • Giảm r đi 1, thêm mn vào out.

Mã nguồn Python

class Solution:
    def solve(self, nums, k):
        l, r = len(nums), k - 1
        out = []
        for _ in range(k):
            mn = nums[~r]
            for i in range(r, l):
                if mn >= nums[~i]:
                    mn = nums[~i]
                    l = i
            r -= 1
            out.append(mn)
        return out

ob = Solution()
nums = [2, 3, 1, 10, 3, 4]
k = 3
print(ob.solve(nums, k))  # Output: [1, 3, 4]

Đầu vào

[2, 3, 1, 10, 3, 4], 3

Đầu ra

[1, 3, 4]