數組列表算法 - 訪談

今天我在一次採訪中被問到了這個問題。我已經嘗試瞭解決方案，但想知道如果有解決這個更好的方法：數組列表算法 - 訪談

問題：我得爲50種萬名元素的ArrayList說使得ArrayList中的每個元素的值是一樣的指數。例如：list.get（0）= 0; list.get（1）= 1 ...等。但是隻有一個元素與這種排序不同步[即list.get（i）！= i]。你如何找到這個元素。

我的答案：使用多個線程在列表中迭代每個線程處理每個線程處理每一次arraylist的拼接每次比較list.get（i）與i。當找到該元素時，設置一些布爾變量來向其他線程表明該元素已被找到。

有沒有辦法解決這個問題，而無需迭代列表？還是更好的方法？

來源

2012-04-26 sachinrahulsourav

沒有關於這個數字可能在列表中的提示，這個問題有點無聊。 – keyser 2012-04-26 14:21:54

我認爲你必須解釋「只有一個元素是不同步的」真的意味着..它沒有意義..請參閱下面的答案。我想如果你移動一個元素，所有剩餘的元素將不同步，不是？ – duedl0r 2012-04-26 14:29:34

@ dued0r元素未被刪除。面試官詢問如何識別價值與指數不一致的因素。 – sachinrahulsourav 2012-04-26 14:54:57

在最糟糕的情況下，您必須檢查每個元素，因此您無法改進時間複雜度。

考慮到這一點，最好的算法是從頭到尾掃描數組列表。這樣你就可以充分利用可用的內存帶寬。

我不完全清楚線程是如何或爲何進入圖片。它似乎不合適。這是問題的一部分嗎？

來源

2012-04-26 14:09:48 NPE

雖然我同意你的觀點，但問題很枯燥。 – 2012-04-26 14:10:32

@aix不，這是我對面試官的回答。我以爲使用數組拼接和處理數組列表的迭代實際上會更好，但是後來我意識到，即使使用多線程，O（n）也不能改進。事實上，線程只會引入更多的複雜性。 – sachinrahulsourav 2012-04-26 14:14:18

儘管您可以在同一個循環中從列表兩端出現問題。 – 2012-04-26 14:16:13

你不能比O(n)做得更好。

其次，我認爲在這些問題中討論線程和多線程是個壞主意。他們根本沒有興趣。最後你有一個運行時間（無論），你的常數被刪除。

也許面試官的意思是一個排序數組，其元素從0到n-1，索引從0到n-1。然後將一個元素移動到不同的位置。但這意味着所有其餘的元素都有不同的索引！在這種情況下，您可以通過二進制搜索來改進您的搜索：

然後您可以在O(log n)中獲取元素。從中間開始，檢查索引是否等於元素。如果與上半部分相同，則不使用其他部分。

來源

2012-04-26 14:11:07 duedl0r

我同意。並且500 000對於單個線程來說現在還不算太多 – keyser 2012-04-26 14:11:43

您的'O（log n）'算法似乎在列表'1,0,2,3,4,5'上失敗。而不是移動，你的意思是刪除？然後它工作。 – btilly 2012-04-26 14:50:18

@btilly我想他的意思是，如果一般規則是f（n + 1）= f（n）+1（除了那個特定的目標），那麼二進制搜索在這裏是理想的。 – HelloWorld 2012-04-26 17:32:51

繼@ AIX的回答，怎麼樣每個循環做2個檢查：

for (int i = 0; i < list.size/2; i++) 
{ 
    if (i != list.get(i)) 
    { 
    return i; 
    } 
    else if (list.size - i != list.get(list.size - i) 
    { 
    return list.size - i; 
    } 
}

來源

2012-04-26 14:19:42

我的觀點是，在沒有性能基準的情況下，循環展開最好留給JIT編譯器。 – NPE 2012-04-26 14:21:09

@aix是的，我同意，純粹在可讀性方面，我會避免做這樣的事情。 – 2012-04-26 14:24:26

1. iterate through the list 
2. check for the condition in the elements 
3. when that only element found break out the loop...

我不認爲線程進入競技場......

來源

2012-04-26 14:23:38 Parth

答案是：一個迭代。你提到原因的併發性是他們正在捕撈的東西。

事實上，自從java 8以後，解決方案是否平行也很簡單。我認爲最會帶來：

OptionalInt foundInt = IntStream.range(0, list.size()) 
    .parallelStream() 
    .filter(i -> i != list.get(i)) 
    .findAny();

來源

2016-08-11 14:49:45

數組列表算法 - 訪談

回答

相關問題