Algorithms
Algorithms copied to clipboard
xiaoyuzdy
Num_1_04_18
可以用lg(n)方法解決，你好好想想，結合數學圖像，某個點如果不是local minimum，那麼這點的圖像要麼是上升坡，要麼是下降坡，上身坡說明，local min在左邊，下降坡度，說明有local min在右邊. 不過題目有問題的地方是。local min不是a[i-1]<a[i]<a[i+1],根據數學應該是a[i]<[a-1] && a[i]<a[i+1].
按你的思路写了一段代码，感觉比较次数并没有减少多少，而且非常的麻烦，要考虑上坡，下坡，还有中间值大于两边的情况，还有一边扫描完继续扫描另一边要防止进入死循环的情况，你看一下吧，我写的感觉很臃肿你可以优化一下https://github.com/xiaoyuzdy/Algorithms/blob/master/AlgorithmsTest/src/Num1_1_04/Num_1_04_18.java 我看了你写的这题是有问题的，比如int a[]={1,2,3,4,5,0,1};在不打乱顺序的情况你试一下会报异常的
我覺得題意應該是默認array中有多個minima吧，所以我用了個random後的大數組，就是默認上升坡度的左邊一定有個min，或下降破的右邊有個min，想的比較簡單。你給的數組，反而會報錯，之前我也是沒想到。不過我這樣只搜一次是lgn，而題目說最差2lgn，所以我覺得答案應該是要兩次binary search，不過我也還沒想到
不知道你看得是英文原版还是中文版的，我看的中文版这题的题意就比较模糊，没说数组中的数据有某种规律，而对于一般的乱序数组我觉得是达不到2lgn的（我想不到有什么办法可达实现这样的目标）