最大xor與最接近的號碼

如果我有一個正整數列表L，我給了另一個號碼K，我需要找到列表中與K XOR最大的數字。最大xor與最接近的號碼

我想到了這個算法。我想用反指令來驗證它的正確性。我的算法是：

查找P = K的補碼（1的補碼）。現在找到列表L中最接近P的數字。讓這個數字爲N.K和N的XOR將是最大的。
給定數字集合中最接近的數字I是一個與I的差值最小的數字。

可以說，對於列表L中的大於P的數字是不正確的。但是數字<=P不正確嗎？

請通過提供反駁論點/建議/想法告訴我我是否正確。

來源

2012-10-20 halkujabra

最近的< - 你如何定義這個？ – nhahtdh

什麼，最接近數字？那麼它當然會是錯誤的。 – nneonneo

@nhahtdh我編輯 – halkujabra

我認爲你需要一種叫做Trie的東西。

考慮K每一位，從高至低，當然我們可以貪婪時確定的答案該位是否可以1，我的意思是，首先你盡力讓1024（甚至更高），以及然後512，然後256然後......最後到最後一位1。

所以首先你需要檢查列表L一些數量是否有相反的價值K最高位，那麼所有選定的號碼中，那麼你需要找到具有相反的價值K號碼第二高位。

現在解決方案很明顯，建立一個Trie與L，確定答案的位從高到低，這對應於在該樹上的旅行。

來源

2012-10-20 16:06:58 Topro

-1

編碼和運行明顯的蠻力算法所花費的時間比您已經花在這上面的時間少得多。

來源

2012-10-20 05:45:09 WaywiserTundish

通常，優化的目的是使其始終快速運行，而不是讓它快速運行一次。 – nneonneo

我沒有看到任何優化的提及。無論如何，XOR在幾乎任何架構上都非常快速 - 嘗試着幹幾個CPU週期毫無意義。 – WaywiserTundish

當然，但你可以做一個預處理'L'的算法，使得對這個'L'的所有查詢都非常快（例如'log（N）'快）。這樣的算法在某些類型的問題中可能是關鍵的（例如，針對大量固定的比特集合的多個最大子集搜索）。在這種情況下，即使異或運算速度很快，10000' O（log（N））'查詢將在10000'O（N）'查詢中擊敗褲子以獲得足夠大的'N'。 – nneonneo

不，不對。

讓K = 0011，這樣P = 1100。讓L = {0011, 1100}。你的算法會選擇N = 1100，這顯然是不正確的，因爲N^K = 0，而0011^N = 3。

來源

2012-10-20 05:46:24 nneonneo

最大xor與最接近的號碼

回答

相關問題