पायथन में न्यूनतम सबमैट्रिक्स ज्ञात करने का प्रोग्राम

मान लीजिए हमारे पास एक 2D मैट्रिक्स और एक अन्य मान k है। हमारा लक्ष्य एक मैट्रिक्स लौटाना है जिसमें सभी k x k सब-मैट्रिक्स के न्यूनतम मान हों।

इसलिए, यदि इनपुट इस प्रकार है:

और k = 2, तो आउटपुट [[3, 5], [3, 3]] होगा।

इनपुट से, हम देख सकते हैं कि ऊपरी बाएं सबमैट्रिक्स का न्यूनतम मान 3 है

3 5
8 6

ऊपरी दाएं सबमैट्रिक्स का न्यूनतम मान 5 है

5 6
6 5

निचले बाएं सबमैट्रिक्स का न्यूनतम मान 3 है

8 6
4 3

निचले दाएं सबमैट्रिक्स का न्यूनतम मान 3 है

6 5
3 12

हल करने के चरण

• प्रत्येक r, row के लिए इंडेक्स r और आइटम row में matrix में, करें

  • q := एक नया डबल एंडेड क्यू

  • nrow := एक नई सूची

  • i के लिए 0 से row के आकार तक की रेंज में, करें

    • यदि q और q[0], i - k के समान है, तो q का बायां आइटम पॉप करें

    • जब तक q और row[q[-1]] > row[i] शून्येतर है, करें q का दायां आइटम पॉप करें

    • i को q के दाएं छोर पर डालें

    • row[q[0]] को nrow के अंत में डालें

  • matrix[r] := nrow

• j के लिए 0 से matrix[0] के आकार तक की रेंज में, करें

  • q := एक नया डबल एंडेड क्यू

  • ncol := एक नई सूची

  • i के लिए 0 से matrix के आकार तक की रेंज में, करें

    • यदि q और q[0], i - k के समान है, तो q का बायां आइटम पॉप करें

    • जब तक q और matrix[q[-1]][j] > matrix[i][j] शून्येतर है, करें q का दायां आइटम पॉप करें

    • i को q के दाएं छोर पर डालें

    • matrix[q[0], j] को ncol के दाएं छोर पर डालें

    • i के लिए 0 से matrix के आकार तक की रेंज में, करें matrix[i, j] := ncol[i]

• ret := matrix के आकार - k + 1 के आकार की एक नई सूची जिसे 0 से आरंभ किया गया है

• i के लिए 0 से ret के आकार तक की रेंज में, करें

  • j के लिए 0 से ret[0] के आकार तक की रेंज में, करें ret[i, j] := matrix[i + k - 1, j + k - 1]

• ret लौटाएं

उदाहरण

import collections

class Solution:
    def solve(self, matrix, k):
        for r, row in enumerate(matrix):
            q = collections.deque()
            nrow = []
            for i in range(len(row)):
                if q and q[0] == i - k:
                    q.popleft()
                while q and row[q[-1]] > row[i]:
                    q.pop()
                q.append(i)
                nrow.append(row[q[0]])
            matrix[r] = nrow
        for j in range(len(matrix[0])):
            q = collections.deque()
            ncol = []
            for i in range(len(matrix)):
                if q and q[0] == i - k:
                    q.popleft()
                while q and matrix[q[-1]][j] > matrix[i][j]:
                    q.pop()
                q.append(i)
                ncol.append(matrix[q[0]][j])
            for i in range(len(matrix)):
                matrix[i][j] = ncol[i]
        ret = [[0] * (len(matrix[0]) - k + 1) for _ in range(len(matrix) - k + 1)]
        for i in range(len(ret)):
            for j in range(len(ret[0])):
                ret[i][j] = matrix[i + k - 1][j + k - 1]
        return ret

ob = Solution()
print(ob.solve(matrix=[
    [3, 5, 6],
    [8, 6, 5],
    [4, 3, 12]
], k=2))

इनपुट

[[3, 5, 6], [8, 6, 5], [4, 3, 12]], 2

आउटपुट

[[3, 5], [3, 3]]