在每個元素出現兩次的給定數組中找到具有最長距離的元素？

給定一個int數組，每個int在數組中正好顯示爲TWICE。找到並返回int，這樣這對int在這個數組中的距離互相最大。在每個元素出現兩次的給定數組中找到具有最長距離的元素？

例如[2, 1, 1, 3, 2, 3]

2: d = 5-1 = 4; 
1: d = 3-2 = 1; 
3: d = 6-4 = 2; 
return 2

我的想法：

使用HashMap的，關鍵是a[i]，和值是指數。掃描a[]，將每個數字放入散列。如果一個數字被擊中兩次，使用它的索引減去舊的數字索引，並使用結果更新散列中的元素值。

之後，掃描散列並返回最大元素（距離）的關鍵。它是時間和空間的O（n）。

如何在O（n）時間和O（1）空間中做到這一點？

來源

2011-12-16 user1002288

我認爲，你可以明顯地使它更快......只是一個提示 - 在你的例子中，在你發現`a [0]`距離是`5`後，你不需要檢查更多的值根本來說，因爲數組的大小是'6'。 – lapk 2011-12-16 07:30:17

@AzzA這可以確保速度，但它不會影響線性漸近增長率。 – 2011-12-16 07:40:52

這是面試問題嗎？ – 2011-12-16 09:18:17

你想擁有最大距離，所以我假設你搜索的數字更可能在開始和結束。這就是爲什麼我會在同一時間從開始和結束循環數組。

[2, 1, 1, 3, 2, 3] 
Check if 2 == 3? 
Store a map of numbers and position: [2 => 1, 3 => 6] 
Check if 1 or 2 is in [2 => 1, 3 => 6] ?

我知道，那甚至不是僞代碼，而不是完整的，但只給了這個想法。

來源

2011-12-16 07:46:08 PiTheNumber

將iLeft索引設置爲第一個元素，將iRight索引設置爲第二個元素。增加iRight索引，直到找到左項目的副本或滿足數組的末尾。在第一種情況下 - 記住距離。

增加iLeft。從新的iRight開始搜索。 iRight的起始價值永遠不會降低。 Delphi代碼：

iLeft := 0; 
    iRight := 1; 

    while iRight < Len do begin //Len = array size 
    while (iRight < Len) and (A[iRight] <> A[iLeft]) do 
     Inc(iRight); //iRight++ 
    if iRight < Len then begin 
     BestNumber := A[iLeft]; 
     MaxDistance := iRight - iLeft; 
    end; 
    Inc(iLeft); //iLeft++ 
    iRight := iLeft + MaxDistance; 
    end;

來源

2011-12-16 12:54:06 MBo

該算法是O（1）空間（有一些作弊行爲），O（n）的時間（平均），需要將光源陣列是非const並在結束破壞它。它也限制了數組中的可能值（每個值的三位應該爲算法保留）。

答案的一半已經在問題中。使用hashmap。如果一個數字被擊中兩次，使用索引差異，更新迄今爲止最好的結果，並將該數字從哈希映射中移除以釋放空間。爲了使其成爲O（1）空間，只需重新使用源數組。將數組轉換爲散列映射。

將數組元素轉換爲散列表單元格之前，請記住它的值和位置。之後它可能會被安全覆蓋。然後使用這個值來計算hashmap中的新位置並覆蓋它。元素被這樣洗牌，直到找到一個空單元。要繼續，請選擇任何尚未重新排序的元素。當一切都重新排序後，每個int對肯定會被擊兩次，這裏我們有一個空的hashmap和一個更新的最佳結果值。

一個保留位用於將數組元素轉換爲散列映射單元。在開始時它被清除。當一個值被重新排序到哈希映射單元格時，該位被設置。如果該位未被設置爲被覆蓋的元素，則該元素僅被接着處理。如果此位設置爲要覆蓋的元素，則會出現衝突，請選取第一個未使用的元素（此位未設置）並覆蓋它。

2個更多的保留位用於鏈接衝突的值。他們對連鎖開始/結束/繼續的位置進行編碼。（有可能優化此算法，以便只需要2個保留位...）

散列表單元格應包含這3個保留位，原始值索引和一些信息以唯一標識此元素。爲了使這成爲可能，散列函數應該是可逆的，以便部分值可以根據其在表格中的位置被恢復。在最簡單的情況下，散列函數只是ceil(log(n))最低有效位。在表中的值由3個字段：

3保留位從原來的值
32 - 3 - (ceil(log(n)))高階位爲原始陣列

時間複雜度在元件的位置

ceil(log(n))位僅爲平均值O（n）;最壞情況下的複雜度是O（n^2）。

該算法的其他變體是將數組順序轉換爲散列映射：在每個步驟m具有2^m數組的第一個元素轉換爲散列映射。當m較低時，某些恆定大小的陣列可能會與散列圖交錯以提高性能。當m很高時，應該有足夠的int對，它們已經被處理，並且不再需要空間。

來源

2011-12-16 14:38:39

在O（n）時間和O（1）空間中沒有辦法做到這一點。

來源

2011-12-19 21:39:06 phkahler

在每個元素出現兩次的給定數組中找到具有最長距離的元素？

回答

相關問題