মান लीजिए हमारे पास कार्ड्स की एक सूची है, और हम उन्हें इस तरह व्यवस्थित करना चाहते हैं कि वे आरोही क्रम में प्रकट हों। जैसा कि हम जानते हैं, कार्ड्स इस तरीके से प्रकट होते हैं: 1. शीर्ष कार्ड को हटाकर प्रकट किया जाता है और फिर अगला कार्ड पीछे चला जाता है। 2. चरण 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 := एक कतार और idx के तत्वों को डालें
- जब तक q शून्येतर है, करें
- q के बाएं से तत्व को हटाएं और order में डालें
- यदि q शून्येतर है, तो
- ans := कार्ड्स के आकार की एक सूची बनाएं, और 0 से भरें
- order के प्रत्येक तत्व i और कार्ड्स के कार्ड के लिए, करें
- ans[i] := कार्ड
- 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]
