Pythonでk番目に大きいXOR座標値を見つけるプログラム

1つのmxn行列があるとします。および別の値k。ここで、行列の座標（a、b）の値は、すべての行列[i、j]のXORです。ここで、iは範囲（0からa）にあり、jは範囲（0からb）にあります。行列のすべての座標のk番目に大きい値（1インデックス）を見つける必要があります。

したがって、入力が次のような場合

また、k =1の場合、座標（0,1）の値は5 XOR 2 =7であり、これが最大であるため、出力は7になります。

これを解決するには、次の手順に従います-

• m：=行数、n：=列数
• 0からm-1の範囲のiの場合、do
  • 0からn-1の範囲のjの場合、do
    • jがゼロ以外の場合、
      • matrix [i、j]：=matrix [i、j] XOR matrix [i、j-1]
• 見た：=新しい地図
• count：=0
• 0からn-1の範囲のiの場合、do
  • 0〜m-1の範囲のjの場合、do
    • jがゼロ以外の場合、
      • matrix [j、i]：=matrix [j、i] XOR matrix [j-1、i]
    • seen [matrix [j、i]] =（可能であれば1 + sawen [matrix [j、i]]、それ以外の場合は1）
    • count：=count + 1
    • カウント>kの場合、
      • min_value：=最小値
      • sawed [min_value]：=saw [min_value]-1
      • sawed [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

出力

7