數組中缺少整數

給定正整數列表，找到不在列表中的最小整數。數組中缺少整數

例如：列表= [7,4,9,1]，答案將是2.

應該是什麼最快的算法（無排序）在列表中未計算的最小整數？

注意整數非常大的列表，所以哈希不可能？

來源

2014-01-08 sp1rs

除此之外，如果你有很嚴重的性能要求，排序之後迭代泡沫應該足夠快。請注意，性能比較可能取決於典型的數組大小和整數值。 –

爲什麼不排序？你可以排序。數組是隻讀的嗎？ –

@dystroy或者如果你在採訪中...... – Dukeling

爲O（n *的log（n））

其運行在O的最簡單的算法（N *的log（n））將是：

排序與快速排序排列爲爲O（n *的log（n））
迭代通過陣列，並找到它是不在列表中最小的元件，其是最大爲O（n）

ö （n）和O（1）額外空間

存在運行在O（n）中的算法。它的工作原理如下：

遍歷你的數組。對於每個正數，我將數組[i]的值設置爲-1。忽略大於數組大小的值
第二次遍歷數組並找到第一個非負數的索引。（O（n））的

來源

2014-01-08 09:50:13

我編輯了我的問題。 – sp1rs

查看應該回答你的問題的編輯 –

如果正數「i」大於數組，那麼將不起作用？該算法修復了 – Ishtar

在一般情況下，我會

排序陣列（選擇相關的排序取決於您的典型陣列或使用適應性的排序功能）
疊代找到第一個缺失整數的數組

來源

2014-01-08 09:50:16

我編輯了我的問題。 – sp1rs

如果數字是唯一您可以在O（nlogn）中使用二進制搜索。缺失值最多爲n。

設置低= 0，高= N，
集A =低+（高至低）之間/ 2
計數值的低和高小於或等於一個
- 如果它是少一半，然後，重複進行高=之間的
計數值的低和高大於
- 如果它小於一半重複FO ř低=一個
否則沒有溶液（所有值都在陣列中）

來源

2014-01-08 10:55:56 Ishtar

不應該爲這個方法排序數組嗎？ –

如果您每次循環遍歷整個陣列，則不適用。這就是爲什麼它是O（nlogn）而不是O（logn） – Ishtar

爲什麼這比僅僅排序和迭代更好？對於O（n）中的算法，請參閱我的回答 –

// Mark arr[i] as visited by making arr[arr[i] - 1] negative. Note that 
// 1 is subtracted because index start from 0 and positive numbers start from 1 
for(i = 0; i < size; i++) 
{ 
    if(abs(arr[i]) - 1 < size && arr[abs(arr[i]) - 1] > 0) 
     arr[abs(arr[i]) - 1] = -arr[abs(arr[i]) - 1]; 
} 

// Return the first index value at which is positive 
for(i = 0; i < size; i++) 
    if (arr[i] > 0) 
     return i+1; // 1 is added becuase indexes start from 0 
}

2步驟算法以從陣列找到最小的正缺少的元素

我們遍歷包含所有正數的數組並標記元素x的存在，我們將索引x處的值的符號更改爲負數。如果x>大小，則忽略x。
我們再次遍歷數組並打印出具有正值的第一個索引。（請記住，這將是指數+ 1陣列從第0索引開始）

Time: O(n) Space: O(1)

來源

2014-07-01 12:35:50 Jerky

數組中缺少整數

回答

相關問題