確定一個數組是否每個都有數字a到b

給定一個大小爲n的數組A和兩個數字a和b與b-a + 1 = n，我需要確定A是否包含每個a和b之間的數字（恰好一次）。例如，如果n = 4且a = 1，b = 4，那麼我期待看看A是否是[1,2,3,4]的重新排列。確定一個數組是否每個都有數字a到b

實際上，我需要用O（1）空間（沒有散列表）來做到這一點。

我的第一個想法是對A進行排序，但是我必須在不重新排列A的情況下執行此操作，所以這已經結束了。

我的第二個想法是一次運行A，將條目加起來並檢查它們是否在正確的範圍內。最後，我必須得到正確的總和（對於a = 1，b = n，這是n（n + 1）/ 2），但是這並不總是適用於所有情況，例如， [1,1,4,4,5]通過n = 5，a = 1，b = 5的測試，但不應該。

我的工作的唯一想法是通過數組n次，確保每次只看到一次數字。有更快的解決方案嗎？

來源

2014-01-26 Daniel

* n *有多大？爲什麼O（1）空間要求？ –

聽起來像面試問題。 – herohuyongtao

不是面試問題或家庭作業。對於大小，n可以達到10^9或更多。我的解決方案有效，但必須有更好的東西。 – Daniel

您可以在數組中單次通過，只使用您已經提到的n(n+1)/2方法的小修改。

爲此，請遍歷數組，忽略a..b範圍外的元素。對於處於正確範圍內的數字，您需要跟蹤三個值：數字總和，數字平方和，以及數字的數量。

您可以預先計算數字總和和平方和（以及普通計數）的正確值。

然後將您的結果與預期結果進行比較。例如，考慮如果你在搜索1,2,3,4。如果你只使用了數字的總和，那麼[1,1,4,4]會產生正確的結果（1 + 2 + 3 +4 = 10,1 + 1 + 4 + 4 = 10），但是如果你還加上了平方和，問題就很明顯了：1 + 4 + 9 + 16 = 30但是1 + 1 + 16 + 16 = 34.

這實質上是應用（至少非常類似於）Bloom過濾器來解決問題。給定一個足夠大的組和一對固定的函數，會出現一些不正確的輸入，這些輸入會產生正確的輸出。您可以通過增加您應用的過濾器數量來將此可能性降低到任意低的值。或者，你可以設計一種不會被愚弄的自適應算法 - 如果你的輸入範圍是N，那麼把每個數字提高到N + 1的功率，可能會保證你只能得到正確的結果與正確的輸入（但我承認，我不是絕對肯定這是正確的）。

來源

2014-01-26 06:58:46

這是小N A好主意，但提高數以10^9 ISN」。牛逼一件容易的事 – Daniel

@Daniel：。取決於有有效地提高數字大權力的方法（廣泛應用於RSA密碼，爲一個例子） –

簡單的例子：這兩套6,5,1和7,3， 2具有平方相等數量，金額和總和。 –

這裏是一個O（1）空間和O（n）的解決方案，它可以幫助： -

查找範圍mean和standard deviation（A，B）
掃描陣列，發現平均和標準差。
如果任何號碼是外部（A，B）返回false
if(mean1!=mean2 || sd1!=sd2) return false else true.

注意：我可能不是100％準確。

來源

2014-01-26 07:17:05

這不是很準確，在所有的n個大的（甚至是100）。 – Daniel

@Daniel我不認爲這取決於n的大小，但越是這樣的分佈的數 –

下面是一個失敗的哈希衝突的可能性的解決方案。

採取一個很好的（例如加密）哈希函數H.

Compute: xor(H(x) for x in a...b) 
Compute: xor(H(A[i]) for i in 1...n)

如果兩者是不同的，那麼可以肯定你沒有置換。如果兩者是相同的，那麼你幾乎可以肯定有一個排列組合。通過在散列中包含一個隨機種子，可以對輸入進行免疫以產生散列衝突。

這顯然是O（B-A）在運行時間，需要O（1）的外部存儲，並容易實現。

來源

2014-01-26 10:42:21

確定一個數組是否每個都有數字a到b

回答

相關問題