Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> Python

Python में k सॉर्टेड सूचियों को मर्ज करें


मान लीजिए हमारे पास कुछ सूचियाँ हैं, ये सॉर्टेड हैं। हमें इन सूचियों को एक सूची में मर्ज करना है। इसे हल करने के लिए, हम हीप डेटा संरचना का उपयोग करेंगे। इसलिए यदि सूचियाँ [1,4,5], [1,3,4], [2,6] हैं, तो अंतिम सूची [1,1,2,3,4,4,5,6] होगी।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −

  • एक हीप बनाएं

  • lists में प्रत्येक लिंक्ड सूची l के लिए −

    • यदि l 0 नहीं है, तो l को हीप में डालें

  • res := null और res_next := null

  • एक अनंत लूप करें −

    • temp := हीप का न्यूनतम

    • यदि हीप में कोई तत्व नहीं है, तो res लौटाएं

    • यदि res 0 है, तो

      • res := temp, res_next := temp

      • temp := temp का अगला तत्व

      • यदि temp शून्य नहीं है, तो temp को हीप में डालें

      • res का अगला := null

    • अन्यथा −

      • res_next का अगला := temp, temp := temp का अगला, res_next := res_next का अगला

      • यदि temp null नहीं है, तो temp को हीप में डालें

      • res_next का अगला := null

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें −

class ListNode: def __init__(self, data, next = None): self.val = data self.next = next def make_list(elements): head = ListNode(elements[0]) for element in elements[1:]: ptr = head while ptr.next: ptr = ptr.next ptr.next = ListNode(element) return head def print_list(head): ptr = head print('[', end = "") while ptr: print(ptr.val, end = ", ") ptr = ptr.next print(']') class Heap: def __init__(self): self.arr = [] def print_heap(self): res = " " for i in self.arr: res += str(i.val) + " " print(res) def getVal(self,i): return self.arr[i].val def parent(self,i): return (i-1)//2 def left(self,i): return (2*i + 1) def right(self,i): return (2*i + 2) def insert(self,value): self.arr.append(value) n = len(self.arr)-1 i = n while i != 0 and self.arr[i].val

इनपुट

[[1,4,5],[1,3,4],[2,6]]

आउटपुट

[1, 1, 2, 3, 4, 4, 5, 6, ]

  1. पायथन में मर्ज सॉर्ट समझाया गया पायथन में मर्ज सॉर्ट समझाया गया

    मर्ज सॉर्ट एक सॉर्टिंग तकनीक है। यह एक कुशल सॉर्टिंग एल्गोरिथम है जिसकी टाइम कॉम्प्लेक्सिटी O(n log n) होती है जहां n सॉर्ट की जाने वाली ऐरे की लंबाई है। मर्ज सॉर्ट एक एल्गोरिथम है जो डिवाइड एंड कंकर पैराडाइम का पालन करता है। यह लगातार ऐरे को दो समान हिस्सों में विभाजित करता है। बाद में यह सिंगल एल

  1. पायथन में इनहेरिटेंस (Inheritance) पायथन में इनहेरिटेंस (Inheritance)

    इस लेख में, हम पायथन 3.x या उससे पहले के संस्करण में इनहेरिटेंस और क्लासेस को एक्सटेंड करने के बारे में जानेंगे।इनहेरिटेंस वास्तविक दुनिया के संबंधों को अच्छी तरह से दर्शाता है, पुन: प्रयोज्यता प्रदान करता है और ट्रांजिटिविटी का समर्थन करता है। यह तेज़ विकास समय, आसान रखरखाव और विस्तार में आसानी प्र

  1. - Python Lists में महारत: निर्माण, एक्सेस, और हेरफेर

    इस ट्यूटोरियल में हम Python Lists के बारे में सीखेंगे; लिस्ट कैसे बनाएं, आइटम्स एक्सेस करें, आइटम्स हटाएं, लिस्ट डिलीट करें और इसी तरह। Python में, लिस्ट्स को स्क्वायर ब्रैकेट्स [] का उपयोग करके बनाया जाता है और लिस्ट में प्रत्येक आइटम को कॉमा , से अलग किया जाता है। Python लिस्ट्स में कई अलग-अलग प्र