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

पायथन में क्रमबद्ध मैट्रिक्स में Kवां सबसे छोटा तत्व

मान लीजिए हमारे पास एक n x n मैट्रिक्स है जहां प्रत्येक पंक्ति और कॉलम बढ़ते क्रम में क्रमबद्ध हैं, हमें मैट्रिक्स में kवां सबसे छोटा तत्व ढूंढना है। ध्यान दें कि यह क्रमबद्ध क्रम में kवां सबसे छोटा तत्व है, kवां अद्वितीय तत्व नहीं। इसलिए यदि इनपुट [[1,5,9],[10,11,13],[12,13,15]] जैसा है, यदि k = 8, तो आउटपुट 13 होगा।

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

  • checkVal() नामक एक मेथड परिभाषित करें और आर्गुमेंट्स मैट्रिक्स और वैल्यू हैं
  • i := 0, j := matrix[0] की लंबाई - 1, counter := 0
  • जबकि i < मैट्रिक्स की लंबाई और j >= 0
    • यदि matrix[i, j] > value, तो j को 1 से घटाएं, अन्यथा counter := counter + j + 1, i को 1 से बढ़ाएं
  • counter लौटाएं
  • मुख्य विधि इस तरह होगी -
  • n := मैट्रिक्स की पंक्ति, high := निचला दायां कोना तत्व, low := ऊपरी बायां कोना तत्व
  • जबकि low <= high, करें
    • mid = low + (high - low)/2
    • count := checkVal(matrix, mid)
    • यदि count < k, तो low := mid + 1, अन्यथा high := mid - 1
  • low लौटाएं

उदाहरण

class Solution(object):
    def kthSmallest(self, matrix, k):
        n = len(matrix)
        high = matrix[n-1][n-1]
        low = matrix[0][0]
        while low <= high:
            mid = low + (high - low) / 2
            count = self.check_value(matrix, mid)
            if count < k:
                low = mid + 1
            else:
                high = mid - 1
        return int(low)
    def check_value(self, matrix, value):
        i = 0
        j = len(matrix[0]) - 1
        counter = 0
        while(i < len(matrix) and j >= 0):
            if matrix[i][j] > value:
                j -= 1
            else:
                counter += j + 1
                i += 1
        return counter

matrix = [[1,5,9],[10,11,13],[12,13,15]]
ob = Solution()
print(ob.kthSmallest(matrix, 8))

इनपुट

matrix =[[1,5,9],[10,11,13],[12,13,15]] k = 8

आउटपुट

13
  1. पायथन में बाइनरी सर्च ट्री में Kवां सबसे छोटा तत्व खोजने का प्रोग्राम पायथन में बाइनरी सर्च ट्री में Kवां सबसे छोटा तत्व खोजने का प्रोग्राम

    मान लीजिए हमारे पास एक बाइनरी सर्च ट्री और एक पूर्णांक k है, हमें ट्री में kवां सबसे छोटा मान ढूंढना है। उदाहरण के लिए, यदि इनपुट निम्न ट्री है: k = 3, तो आउटपुट 7 होगा। इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे (इटरेटिव इनऑर्डर ट्रैवर्सल): stack := [], i := 0, ans := -1। जब तक stack खाली

  1. पायथन में BST में Kवां सबसे छोटा एलिमेंट पायथन में BST में Kवां सबसे छोटा एलिमेंट

    मान लीजिए हमारे पास एक बाइनरी सर्च ट्री है। हमें उस BST में Kवां सबसे छोटा एलिमेंट ढूंढना है। इसलिए यदि ट्री इस तरह है - इसलिए यदि हम 3रा सबसे छोटा एलिमेंट ढूंढना चाहते हैं, तो k = 3, और परिणाम 7 होगा। इसे हल करने के लिए, हम इन चरणों का पालन करेंगे - nodes नामक एक खाली लिस्ट बनाएं solve(root, node

  1. Python प्रोग्राम से क्रमबद्ध सूची में तत्व डालना Python प्रोग्राम से क्रमबद्ध सूची में तत्व डालना

    इस लेख में, हम नीचे दिए गए समस्या कथन के समाधान के बारे में जानेंगे। समस्या कथन - हमें एक सूची दी गई है, हमें क्रमबद्ध क्रम को बदले बिना सूची में एक तत्व डालने की आवश्यकता है। नीचे चर्चा किए गए दो दृष्टिकोण हैं। दृष्टिकोण 1: ब्रूट-फोर्स विधि उदाहरण n: index = i break