查找頂部的log（n）或頂部SQT（n）的值的整數數組

你明白這個問題的意思查找頂部的log（n）或頂部SQT（n）的值的整數數組

查找頂部的log（n）或頂部SQT（n）的值不到線性時間。

如果你不這樣做，這裏是問題http://www.careercup.com/question?id=9337669。

請幫我理解這個問題，然後解決。（雖然有一次我明白我可能也會解決它）

感謝您的時間。

來源

2011-12-21 Aj Gauravdeep

假設數組未被排序，這個問題是Omega(n)，因爲您需要讀取所有元素[在未排序的數組中找到max是Omega(n)問題，並且這個問題不容易找到最大值]。所以，它沒有次線性的解決方案。

有O(n) [線性]溶液，使用selection algorithm

1. find the log(n) biggest element. //or sqrt(n) biggest element... 
2. scan the array and return all elements bigger/equal it.

（*）該僞代碼是不正確的，如果該數組包含易受騙，但在第二步驟中修整愚弄是相當容易的。

來源

2011-12-21 08:18:54 amit

感謝您的解釋阿米特。我無法理解這個「掃描數組並返回所有元素大小/等於它」。這裏的'它'是什麼意思？如果我理解清楚這個問題是否希望我返回數組中的所有元素，它們是> top log（n）或top sqt（n）？ Emilio上面提到，他們希望我做的就是返回sqt [數組中最大的元素]。 – 2011-12-21 16:29:24

'它'是在步驟（1）找到的元素。這個問題要求所有大於'log（n）/ sqrt（n）'的值，因爲它表示：「查找頂部日誌（n）或頂部sqt（n）值....」和**不是**： '找到頂部日誌（n）或頂部sqt（n）值'[要求值** s **而不是值] – amit 2011-12-21 16:59:35

得到它阿米特。非常感謝。 – 2011-12-21 21:05:04

對於非排序數組，複雜度是線性的，但可以通過觀察log（n）和sqrt（n）都是單調增長函數來提高性能，因此max（log（n））.. ）也是log（max（n，...）），對於sqrt也是一樣的。

所以，只需找到max（n）（線性）並計算log和sqrt。

來源

2011-12-21 08:50:16

當然我們假設正的非零整數。 – 2011-12-21 09:02:26

@ edA-qamort-ora-y：true，但我對「費率」不感興趣，只是爲了找到一個峯值。 – 2011-12-21 09:03:47

理解了這個問題。謝謝。 – 2011-12-21 16:23:55

查找頂部的log（n）或頂部SQT（n）的值的整數數組

回答

相關問題