मान लीजिए हमारे पास nums नामक संख्याओं की एक लिस्ट है और एक मान k है, हमें आकार k का लेक्सिकोग्राफिकली सबसे छोटा सबसीक्वेंस ढूंढना है।
उदाहरण के लिए, यदि इनपुट nums = [2, 3, 1, 10, 3, 4], k = 3 है, तो आउटपुट [1, 3, 4] होगा।
समाधान दृष्टिकोण
इस समस्या को हल करने के लिए हम ग्रीडी दृष्टिकोण का उपयोग करेंगे:
- l := 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]
