在寬範圍的整數數組中尋找第一個重複元素？

這個問題是關係到Find the first un-repeated character in a string在其中輸入字符數組，我們可以採取大小256在寬範圍的整數數組中尋找第一個重複元素？

的散列但是，如果

數組中的元素是大範圍的整數，哈希什麼可能會非常昂貴。
該數組包含異構元素，整數或字符，那麼散列如何解決這個問題。

我們可以使用掃描整個陣列的每個元件的蠻力方法，但在最壞的情況下所花費O（N²）。

還有其他想法嗎？

來源

2013-02-20 Prakhar

首先要排序嗎？ – MatthewD 2013-02-20 05:55:26

@MthethewD可能無法正常工作。它返回重複的元素，但可能不是第一個元素。 – Prakhar 2013-02-20 06:00:58

您必須複製數組，以便可以遍歷它以識別第一個重複元素。但你不想使用任何'外部'數組... – MatthewD 2013-02-20 10:46:20

甲離線版本：排序這樣的載體：

vector<std::pair<int,int> > data; 
for (int i=0;i<orignalVec.size();++i) 
    data.push_back(make_pair(originalVec[i] , i));

然後通過向量掃描，尋找一對，其第一值是相同的，並且位置值是最小的。這給出了一個在線版本O(NlogN)

。使用std::map（O(NlogN)）std::unordered_map（O(N)）。

如果數組中的元素是寬範圍的整數，則散列可能非常昂貴。

爲什麼？哈希是旨在解決這個問題是不是？

如果數組包含異構元素，整數或字符，那麼散列如何解決這個問題。

爲這些中的每一個寫入不同的散列函數。對於像int，float，std::string類型我認爲STL內置散列。

對於元素不支持的異構容器比較操作，散列是我能想到的唯一的東西。

來源

2013-02-20 05:52:39 phoeagon

實際上你的解決方案似乎是正確的，因爲你正在考慮重複元素的最小位置值。因爲我不知道矢量事物，所以我沒有得到它。你可以用算法或僞代碼解釋嗎？感謝您的建議。 – Prakhar 2013-02-20 09:28:34

@PrakharBansal'std :: vector'只是一個可變長度的數組。 – phoeagon 2013-02-20 09:41:46

int[] numbers = {1, 5, 23, 2, 1, 6, 3, 1, 8, 12, 3}; 
Arrays.sort(numbers); 

for (int i = 1; i < numbers.length; i++) { 
    if (numbers[i - 1] == numbers[i]) { 
     System.out.println("Repeated numbers are : " + numbers[i]); 
    } 
}

來源

2015-11-08 10:21:21 Krishna

如果你添加一些評論，而不是隻是拋出代碼，那最好。 – 2015-11-08 10:26:43

在寬範圍的整數數組中尋找第一個重複元素？

回答

相關問題