मान लीजिए हमारे पास कार्ड्स की एक सूची है, और हम उन्हें इस तरह क्रमबद्ध करना चाहते हैं कि वे आरोही क्रम में प्रकट हों। जैसा कि हम जानते हैं, कार्ड्स इस तरीके से प्रकट होते हैं:
- सबसे ऊपर का कार्ड हटाया जाता है और प्रकट किया जाता है, फिर अगला कार्ड पीछे चला जाता है।
- चरण 1 को तब तक दोहराया जाता है जब तक कोई कार्ड नहीं बचता।
हमें कार्ड्स का एक ऐसा क्रम ढूंढना है जिससे वे आरोही क्रम में प्रकट हों।
उदाहरण के लिए, यदि इनपुट है cards = [1, 2, 3, 4, 5, 6, 7, 8], तो आउटपुट होगा [1, 5, 2, 7, 3, 6, 4, 8], क्योंकि:
- 1 हटाया जाता है और 5 पीछे चला जाता है, वर्तमान स्थिति:
[2, 7, 3, 6, 4, 8, 5] - 2 हटाया जाता है और 7 पीछे चला जाता है, वर्तमान स्थिति:
[3, 6, 4, 8, 5, 7] - 3 हटाया जाता है और 6 पीछे चला जाता है, वर्तमान स्थिति:
[4, 8, 5, 7, 6] - 4 हटाया जाता है और 8 पीछे चला जाता है, वर्तमान स्थिति:
[5, 7, 6, 8] - 5 हटाया जाता है और 7 पीछे चला जाता है, वर्तमान स्थिति:
[6, 8, 7] - 6 हटाया जाता है और 8 पीछे चला जाता है, वर्तमान स्थिति:
[7, 8] - 7 हटाया जाता है और केवल एक कार्ड
[8]बचता है। फिर[8]हटाया जाता है।
हल करने के चरण
- कार्ड्स की सूची को क्रमबद्ध करें।
idx:= 0 से कार्ड्स की लंबाई तक के तत्वों वाली सूची।order:= एक नई सूची।q:= एक कतार (queue) जिसमेंidxके तत्व डाले जाएं।- जब तक
qशून्येतर है:qके बाएं से तत्व हटाकरorderमें डालें।- यदि
qशून्येतर है, तोqके बाएं से तत्व हटाकरqके अंत में डालें।
ans:=cardsके आकार की सूची, 0 से भरी हुई।orderके प्रत्येक तत्वiऔरcardsके प्रत्येकcardके लिए:ans[i] := card
ansलौटाएं।
उदाहरण
from collections import deque
class Solution:
def solve(self, cards):
cards.sort()
idx = [i for i in range(len(cards))]
order = []
q = deque(idx)
while q:
order.append(q.popleft())
if q: q.append(q.popleft())
ans = [0 for _ in cards]
for i, card in zip(order, cards):
ans[i] = card
return ans
ob = Solution()
print(ob.solve([1, 2, 3, 4, 5, 6, 7, 8]))
इनपुट
[1, 2, 3, 4, 5, 6, 7, 8]
आउटपुट
[1, 5, 2, 7, 3, 6, 4, 8]