Pythonの配列から要素を使用して最大XORを見つけるプログラム

負でない値を持つnumsという配列があるとします。また、querys [i]がペア（xi、mi）を持つquerysという別の配列もあります。 i番目のクエリの答えは、xiの最大ビット単位XOR値と、mi以下のnumsの要素です。 numsのすべての要素がmiより大きい場合、答えは-1です。したがって、答えのサイズがクエリのサイズと同じで、answer[i]がi番目のクエリの答えである配列の答えを見つける必要があります。

したがって、入力がnums =[0,1,2,3,4]クエリ=[[3,1]、[1,3]、[5,6]]の場合、出力は[3、 3,7]、なぜなら

• 0と1は1以下です。0XOR3=3と1XOR3 =2、ここではこれら2つのうち大きい方が3です。

• 1 XOR2=3。

• 5 XOR2=7。

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

• m：=numsのサイズ

• n：=クエリのサイズ

• クエリ=インデックスiごとにトリプレット（i、x、制限）を作成し、クエリでペア（x、制限）を作成します

• 制限に基づいてクエリを並べ替える

• nums：=リストを並べ替えるnums

• res：=サイズnの配列で、0で埋める

• 31から0の範囲のkの場合、1ずつ減らします。

  • プレフィックス：=新しいセット

  • j：=0

  • クエリの各インデックスiと値（x、limit）について、実行します

    • j<=m-1およびnums[j]<=制限、実行

      • nums [j]を右kビットにシフトし、プレフィックスに挿入します

      • j：=j + 1

    • プレフィックスが空の場合、

      • res [i]：=-1

    • それ以外の場合

      • res [i] =res [i]/2の商

      • ターゲット：=res [i] XOR 1

      • （kビットを右にシフトした後のx）XORターゲットがプレフィックスにある場合、

        • res [i]：=target

• 解像度を返す

例

理解を深めるために、次の実装を見てみましょう

def solve(nums, queries):
   m, n = len(nums), len(queries)
   queries = sorted(((i, x, limit) for i, (x, limit) in
enumerate(queries)), key=lambda x: x[2])
   nums = sorted(nums)
   res = [0] * n
   for k in range(31, -1, -1):
      prefixes = set()
      j = 0
      for i, x, limit in queries:
         while j <= m - 1 and nums[j] <= limit:
            prefixes.add(nums[j] >> k)
            j += 1
         if not prefixes:
            res[i] = -1
         else:
            res[i] <<= 1
            target = res[i] ^ 1
            if (x >> k) ^ target in prefixes:
               res[i] = target
   return res

nums = [0,1,2,3,4]
queries = [[3,1],[1,3],[5,6]]
print(solve(nums, queries))

入力

[0,1,2,3,4], [[3,1],[1,3],[5,6]]

出力

[3, 3, 7]