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

मान लीजिए कि हमारे पास एक 2D मैट्रिक्स है और दूसरा मान k है। हमारा लक्ष्य एक ऐसा मैट्रिक्स लौटाना है जिसमें सभी k x 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 के लिए, अनुक्रमणिका r में पंक्ति और मैट्रिक्स में आइटम पंक्ति, करें

  • q :=एक नई डबल एंडेड कतार

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

  • मैं के लिए 0 से पंक्ति के आकार की सीमा में, ऐसा करें

    • अगर q और q[0] i - k के समान है, तो

      • q का सबसे बायां आइटम पॉप करें

    • जबकि q और row[q[-1]]> row[i] गैर-शून्य है, करें

      • q का सबसे दाहिना आइटम पॉप करें

    • q के दाहिने सिरे पर i डालें

    • पंक्ति डालें[q[0]] nrow के अंत में

  • मैट्रिक्स [आर]:=nrow

• j के लिए 0 से लेकर मैट्रिक्स के आकार तक[0], करें

  • q :=एक नई डबल एंडेड कतार

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

  • मैं के लिए 0 से लेकर आव्यूह के आकार तक के लिए, करें

    • अगर q और q[0] i - k के समान है, तो

      • q का सबसे बायां आइटम पॉप करें

    • जबकि q और मैट्रिक्स[q[-1]][j]> मैट्रिक्स[i][j] गैर-शून्य है, करें

      • q का सबसे दाहिना आइटम पॉप करें

    • q के दाहिने सिरे पर i डालें

    • ncol के दाएँ छोर पर मैट्रिक्स [q[0],j] डालें

    • मैं के लिए 0 से लेकर आव्यूह के आकार तक के लिए, करें

      • मैट्रिक्स [i, j] :=ncol[i]

• ret :=मैट्रिक्स के आकार की एक नई सूची - k + 1 को 0 से प्रारंभ किया गया

• मैं के लिए 0 से रिट के आकार की सीमा में, करते हैं

  • j के लिए 0 से लेकर ret के आकार तक[0], करें

    • ret[i, j] :=मैट्रिक्स[i + k-1, j + k-1]

• वापसी रिट

उदाहरण

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

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]]