पायथन में k-th सबसे बड़ा XOR समन्वय मान खोजने का कार्यक्रम

मान लीजिए हमारे पास एक m x n आव्यूह है। और दूसरा मान k. यहां मैट्रिक्स के निर्देशांक (ए, बी) का मान सभी मैट्रिक्स का एक्सओआर है [i, j] जहां i रेंज में (0 से a) और j रेंज में (0 से b)। हमें मैट्रिक्स के सभी निर्देशांकों का kवां सबसे बड़ा मान (1-अनुक्रमित) ज्ञात करना है।

तो, अगर इनपुट पसंद है

5	2
1	6

और k =1, तो आउटपुट 7 होगा क्योंकि निर्देशांक (0,1) का मान 5 XOR 2 =7 है, और यह सबसे बड़ा है

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

m :=पंक्ति गणना, n :=स्तंभ गणना
0 से m-1 की सीमा में i के लिए
- जे के लिए 0 से n -1 की सीमा में, करो
  - यदि j शून्य नहीं है, तो
    - मैट्रिक्स[i, j] :=मैट्रिक्स[i, j] XOR मैट्रिक्स[i, j-1]
देखा:=एक नया नक्शा
गिनती :=0
मैं के लिए 0 से n -1 की सीमा में, करो
- जे के लिए 0 से एम -1 की सीमा में, करो
  - यदि j शून्य नहीं है, तो
    - मैट्रिक्स[j, i] :=मैट्रिक्स[j, i] XOR मैट्रिक्स[j-1, i]
  - seen[matrix[j, i]] =(1+seen[matrix[j, i]] अगर हो सके तो 1)
  - गिनती :=गिनती + 1
  - अगर गिनती> k, तो
    - min_value :=न्यूनतम देखा गया
    - देखा[min_value] :=देखा[min_value] - 1
    - यदि देखा जाए [min_value] 0 है, तो
      - देखे से min_value-वें तत्व हटाएं
कम से कम देखे गए रिटर्न

उदाहरण

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

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