什麼是在隨機數組中找到最大數字的最佳方法？

面試官問我如何在隨機數組中找到最大數字。我回答了整個陣容，以找到最大的數字，但他表示這將花費太多時間。我想知道是否有更好的解決方案。任何建議？什麼是在隨機數組中找到最大數字的最佳方法？

來源

2014-01-20 user228229

如果通過「隨機數組」，他的意思是「一個隨機選擇的值的數組，沒有其他限制（例如排序）」，那麼不，沒有更快的方法。 –

沒有其他辦法。您需要查看每個號碼一次，因爲沒有信息可以確定未看到的號碼是否較小。 – nhahtdh

也許這是一個詭計的問題，讓你推遲並告訴他沒有更快的方法。 – yshavit

您將需要查看數組中的每個元素，因爲它是未排序的。我認爲當面試官說會花很長時間時，你應該說，「是的，這可能需要很長時間，但這是唯一的方法。」

來源

2014-01-20 23:48:32

如果數組中的項是隨機的，那麼最大數可能在任何位置，因此您需要讀取數組中的每個項目以找到最大數。根據假設，你的建議是最有效的方法...

來源

2014-01-20 23:48:36 assylias

int [] random = new int [] {1,2,3}; Arrays.asList（隨機）將排序列表，然後在排序列表上執行BINARY SEARCH .....我之所以問的原因是因爲我可以確定你知道這個答案，但是fir sime理由使它回退。 – zee

如果列表已排序，則不需要執行二分搜索 - 只需查看結尾（或開頭，如果按降序排序）。但分揀需要花費更多的時間，而不是僅僅瀏覽一次。它應該是一個可行的答案，如果需求是其他類似的操作也會發生（「找到我最小的數字」，「找到我的中位數」，「找到我第473個最小的數字」），這樣就值得使投資進行分類。 – yshavit

我不認爲Arrays.asList（數組）排序數組。無論如何排序是O（n日誌n），但循環數組一次是O（n）。所以這是最快的選擇。 – HectorLector

這很可能是面試官用來讓你承受壓力和「展示堅果」的伎倆，捍衛你的答案。

沒有更快的方法來做到這一點，如果你不瞭解數組，除了它被排序。如果這些值以某種方式排序或預先組織，它可能看起來不同。

來源

2014-01-20 23:49:09 poitroae

如果陣列很大，是更快的方式 - 在CPU週期方面不是更快，但在掛鐘方面更快。您可以將數組細分爲多個部分（不是通過複製它，而是通過識別開始/結束點），然後在單獨的線程中搜索每個部分。當所有線程完成後，找到每個找到的最大號碼。這樣，您就可以將問題快速解決X倍，其中X是您計算機上的內核數量。

來源

2014-01-20 23:51:13 yshavit

您的面試官可能希望您深入細節。當我面試某人時，我會找人提出這些問題：

有多少個號碼？
數組中值的範圍是什麼？
數組是排序的嗎？（是的，真的）
數據從哪裏來？
這需要多久運行一次？

我可能會回答：「他們年齡在15到99歲之間，而且他們有1億。」這將導致一個明顯的優化：如果你看到一個99，打破你的循環，並返回99.這可以節省很多時間。如果數字均勻分佈（你應該問問！），這將需要從100,000,000到100以下的物品的平均數量。

我所尋找的是問題。我不希望有人跳進來做他們認爲「正確」的事情，而不知道細節。

即使沒有愚蠢的限制，一個好的候選人會試圖找出這種類型的系統將適合。顯然，在數組中找到最高的數字不會是一次性的事情。如果我需要反覆獲取下一個最高數字，則首先對它進行排序是有道理的。如果陣列將會增長，並且我需要繼續拔出最高，那麼堆是有意義的。

你永遠不會知道你的面試官在想什麼，因爲你沒有向下鑽取。這可能是她一直在尋找的，你的問題。但即使她沒有，即使她只是在摸索這個問題，通過確定細節，你就會證明你知道你在說什麼。

來源

2014-01-20 23:52:04

也許他正在測試你的算法知識。

你的方法可能需要O（n），還有其他排序算法可以將這個隨機數組排序成一個有序數組，例如quicksort可以進行O（nlogn）比較。它可能有一個不好的最壞情況，但這很少見。

在訪談中，我發現最好總結出你的想法，你的假設是你的邏輯，以便你的面試官處於循環之中，並且瞭解你的想法。

來源

2014-01-21 00:20:48 SeekingAlpha

什麼是在隨機數組中找到最大數字的最佳方法？

回答

相關問題