的運動了解的運行時間分析，下面是我在尋找一個答案的問題：從CLRS
數組A [1個... N]包含所有從0到n的整數只有一個除外。通過使用輔助數組B [0 ... n]來記錄哪些數字出現在A中，可以很容易地確定O（n）時間中缺失的 整數。但是，在這個 問題中，我們無法訪問整個整數在一個單一的操作。 A的元素爲 ，用二進制表示，我們唯一可用來訪問它們的操作是「獲取A [i]的第j位」，其中 需要恆定的時間。 顯示如果我們只使用這個操作，我們仍然可以在O（n）時間內確定缺失的整數。
我有這樣的想法： 如果我沒有上面的提取限制，我會採取所有的數字，並將它們異或。然後將結果與1..n中的所有數字進行異或運算。結果會是我的答案。 同樣在這個問題中，我可以在數組中的所有元素之間以log（n + 1）位的距離重複XOR不同數字的位，然後將它們與元素1 ... n異或，但複雜性出來在我看來是O（nlogn）。
如何實現O（n）的複雜性？ 感謝
您可以使用radix sort的變化：根據MSB（最高有效位）
排序號碼你得到尺寸N/2的兩個列表，N/2-1。您可以使用n/2個元素「刪除」列表 - 缺少的數字不在那裏。
重複第二個MSb等。
最後，您選擇的「路徑」（每個位的列表較小）將表示缺少的數字。
複雜性是O(n + n/2 + ... + 2 + 1)，由於n + n/2 + .. + 1 < 2n - 這是O(n)
這個答案假設爲簡單起見，該n=2^k對於一些整數k（這放鬆以後可以下車，做S「特殊」手柄MSb）。
你有n個整數範圍[0..n]。您可以檢查每個數字的最高有效位，並將這些數字分成組C（MSB 0）和D（MSB 1）。由於您知道範圍是[0..n]，因此您可以計算在此範圍內有多少個MSB爲0的數字，稱爲S1，以及此範圍內有多少個MSB 1的數字，稱爲S2。如果C的大小不等於S1，那麼你知道丟失的數字有MSB 0.否則，你知道丟失的數字有MSB 1.然後，你可以遞歸地解決這個問題。由於每次遞歸調用都需要線性時間，並且除第一次遞歸調用外，每次遞歸調用都可以減半問題大小，因此總運行時間爲線性。