পাইথনে ন্যূনতম সাবমেট্রিক্স খুঁজে বের করার জন্য প্রোগ্রাম

ধরুন আমাদের একটি 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-এর জন্য, সূচী r-এ সারি এবং ম্যাট্রিক্স-এ আইটেম সারি, করুন

  • q :=একটি নতুন ডবল শেষ সারি

  • nrow :=একটি নতুন তালিকা

  • আমি 0 থেকে সারির আকারের মধ্যে, কর

    • যদি q এবং q[0] একই হয় i - k, তাহলে

      • q

        -এর বাঁদিকের আইটেমটি পপ করুন

    • যখন q এবং সারি [q[-1]]> সারি [i] অ-শূন্য, কর

      • q

        এর ডানদিকের আইটেমটি পপ করুন

    • q

      এর ডান প্রান্তে i ঢোকান

    • nrow এর শেষে সারি [q[0]] ঢোকান

  • ম্যাট্রিক্স[r] :=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 থেকে ret এর আকারের জন্য, করুন

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