O（n）的算法，返回數組的索引，如果條件爲真

我試圖寫一個算法，需要的線性陣列，排序從最低到最高。它應該返回值的位置如果ARR [Ⅰ] - ARR [J] = 160O（n）的算法，返回數組的索引，如果條件爲真

我的問題是運行時應該是O（N）。

如果我有一個for循環，從最高變爲最低的數組元素，併爲相應的數組元素中的每個元素的搜索使用二進制搜索，運行時仍然爲O（n的log 2 N）做到這一點。

我怎樣才能減少複雜性爲O（n）？

2016-01-06 njok

也許您可以更詳細地向我們展示您嘗試過的方法以及您對如何改進解決方案的想法。這聽起來很像一個家庭作業問題，所以人們可能會更渴望幫助你，而不是爲你寫程序。另請參閱http://stackoverflow.com/help/mcve（現在阿米特很快就回答了這個問題，但對於將來的問題，請查看該鏈接）。 – dfri

@dfri恕我直言，問題很好。他確實展示了一個嘗試性的解決方案+分析了它的複雜性，並得出結論，這不夠好。只有這樣，他才問及如何改進。對我來說似乎很好。 – amit

這個問題可能是http://cs.stackexchange.com/ – wil93

它可以與兩個迭代器，i,j，這樣i > j做到始終，並且增加了i如果arr[i] - arr[j] > 160，並增加j如果arr[i] - arr[j] < 160（如果它等於160，你中止）。

i = 1 
j = 0 
while (i < n): 
    if (arr[i] - arr[j] == 160: 
     // found it! 
    else if (arr[i] - arr[j] < 160): 
     i++ 
    else: 
     j++

來源

2016-01-06 18:26:26 amit

哦，你只是做了那傢伙的功課對他來說更適合！ – pabrams

@pabrams [家庭作業問題在這裏很好]（http://meta.stackoverflow.com/q/255477/572670）。所有的問題都需要展示研究的努力，而這個問題的確如此 - 通過指出一個解決方案，分析它的複雜性，並觀察它的問題。這個問題很好，恕我直言。 – amit

我並不是說任何規則都在這裏被打破，對他來說似乎太簡單了。他本可以通過自己解決這個問題學到更多東西。 – pabrams

O（n）的算法，返回數組的索引，如果條件爲真

回答

相關問題