用于在 Python 中查找大小为 k 的字典序最小子序列的程序

假设我们有一个数字列表 nums 和另一个值 k，我们需要找到大小为 k 的字典序最小子序列。

因此，如果输入类似于 nums = [2, 3, 1, 10, 3, 4] k = 3，则输出将为 [1, 3, 4]

为了解决这个问题，我们将遵循以下步骤：

  • l := nums 的大小，r := k - 1
  • out := 一个新列表
  • 对于 j 的范围从 0 到 k 执行
    • mn := nums[r 的补数]
    • 对于 i 的范围从 r 到 l 执行
      • 如果 mn >= nums[i 的补数]，则
        • mn := nums[i 的补数]
        • l := i
    • r := r - 1
  • 将 mn 插入 out 的末尾
  • 返回 out

示例（Python）

让我们看看以下实现以更好地理解：

 在线演示

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]

更新于：2020 年 12 月 12 日

275 次浏览

启动您的 职业

完成课程即可获得认证

立即开始
广告