L正の整数のリストがあり、別の数値が与えられたK場合、XORKが最大になるリスト内の数値を見つける必要があります。
そのためのアルゴリズムを考えました。反論でその正しさを検証したい。私のアルゴリズムは次のとおりです。
P=K の補数 (1 の補数) を求めます。次に、リスト L で P に最も近い数を見つけます。この数を N とします。K と N の XOR は最大になります。Iは、I との差が最小である数です。たとえば、Pリストよりも大きい数値は正しくありませんL。でも数字的には合ってない<=P？
反論/提案/アイデアを提供して、私が正しいかどうか教えてください.
と呼ばれるものが必要だと思いますTrie。
のすべてのビットを、より高いものからより低いものまで考慮してくださいK。もちろん、このビットの答えが になるかどうかを判断するとき、私たちは貪欲になることができ1ます。 ……やっと最後まで。10245122561
Lしたがって、最初にリスト内の数値の最上位ビットに反対の値があるかどうかを確認する必要があります。次に、選択したすべての数値の中から、2 番目に高いビットにK反対の値を持つ数値を見つける必要があります。K
これで解決策は明らかです。 で を構築しTrie、L答えのビットを上位から下位に決定します。これは、そのツリー上の移動に対応します。
いいえ、正しくありません。
K = 0011、そうしましょうP = 1100。しましょうL = {0011, 1100}。あなたのアルゴリズムはを選択しますN = 1100が、これは明らかに間違っていN^K = 0ます0011^N = 3。
明らかなブルートフォースアルゴリズムのコーディングと実行は、これまでに費やした時間よりもはるかに短い時間で済みます。