โปรแกรมหาลำดับย่อยเล็กซิโครกราฟิกที่เล็กที่สุดขนาด k ใน Python

สมมติว่าเรามีรายการตัวเลข nums และค่า k เราต้องการหาลำดับย่อย (subsequence) ขนาด k ที่เล็กที่สุดในลำดับเล็กซิโครกราฟิก (lexicographically smallest)

เช่น ถ้าข้อมูลนำเข้าคือ nums = [2, 3, 1, 10, 3, 4] k = 3 ผลลัพธ์จะเป็น [1, 3, 4]

ขั้นตอนการแก้ปัญหา (Greedy + Two Pointers)

• l := len(nums), r := k - 1
• out := []
• วน j = 0..k-1:
  • mn := nums[~r] (ดูจากขวาสุดของช่วงที่เหลือ)
  • วน i = r..l-1:
    • ถ้า mn >= nums[~i]: mn := nums[~i], l := i
  • r := r - 1
  • เพิ่ม mn เข้า out
• คืน out

ตัวอย่างโค้ด

class Solution:
    def solve(self, nums, k):
        l, r = len(nums), k - 1
        out = []
        for j 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))

ข้อมูลนำเข้า

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

ผลลัพธ์

[1, 3, 4]