পাইথনে k-তম বৃহত্তম XOR স্থানাঙ্কের মান খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের একটি m x n ম্যাট্রিক্স আছে। এবং আরেকটি মান k. এখানে ম্যাট্রিক্সের স্থানাঙ্কের (a, b) মান হল সমস্ত ম্যাট্রিক্সের XOR [i, j] যেখানে i রেঞ্জে (0 থেকে a) এবং j রেঞ্জে (0 থেকে b)। আমাদের ম্যাট্রিক্সের সমস্ত স্থানাঙ্কের kth বৃহত্তম মান (1-সূচীযুক্ত) খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুট মত হয়

5	2
1	6

এবং k =1, তাহলে আউটপুট হবে 7 কারণ স্থানাঙ্কের মান (0,1) হল 5 XOR 2 =7, এবং এটি সবচেয়ে বড়

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

m :=সারি গণনা, n :=কলাম গণনা
আমি 0 থেকে m - 1 রেঞ্জের জন্য, কর
- করুন
  - যদি j অ-শূন্য হয়, তাহলে
    - ম্যাট্রিক্স[i, j] :=ম্যাট্রিক্স[i, j] XOR ম্যাট্রিক্স[i, j-1]
দেখা হয়েছে :=একটি নতুন মানচিত্র
গণনা :=0
আমি 0 থেকে n - 1 রেঞ্জের জন্য, কর
- করুন
  - যদি j অ-শূন্য হয়, তাহলে
    - ম্যাট্রিক্স[j, i] :=ম্যাট্রিক্স[j, i] XOR ম্যাট্রিক্স[j-1, i]
  - দেখা[ম্যাট্রিক্স[জে, আই]] =(1+দেখা[ম্যাট্রিক্স[জে, আই]] সম্ভব হলে, অন্যথায় 1)
  - গণনা :=গণনা + 1
  - যদি গণনা> k, তারপর
    - min_value :=সর্বনিম্ন দেখা
    - দেখেছি[মিন_মান] :=দেখা[মিন_মান] - ১
    - যদি দেখা হয়[min_value] 0 হয়, তাহলে
      - দেখা থেকে min_value-th উপাদান মুছুন
নূন্যতম দেখা রিটার্ন

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

def solve(matrix, k):
   m, n = len(matrix), len(matrix[0])
   for i in range(m):
      for j in range(n):
         if j:
            matrix[i][j] ^= matrix[i][j-1]

   seen = {}
   count = 0
   for i in range(n):
      for j in range(m):
         if j:
            matrix[j][i] ^= matrix[j-1][i]

         seen[matrix[j][i]] = seen.get(matrix[j][i], 0) + 1
         count += 1

         if count > k:
            min_value = min(seen)
            seen[min_value] -= 1
            if not seen[min_value]:
               seen.pop(min_value)

   return min(seen)
matrix = [[5,2],[1,6]]
k = 1
print(solve(matrix, k))

ইনপুট

[[5,2],[1,6]], 1