一個數(shù)組先升序再降序，求最大值？例如[1,2,2,2,2,3,1]，用最優(yōu)時間復雜度，算法實現(xiàn)獲取最大值3
1 回答
心有法竹
TA貢獻1866條經(jīng)驗 獲得超5個贊
兩種方案吧
第一種遍歷一次，找到開始變小的那個i，a[i-1]就是最大值，復雜度O(n);
第二種，二分法，先去中間的三個值，判斷這三個值是否單調(diào)，如果不是單調(diào)，中間那個就是最大值，否則根據(jù)單調(diào)方向，找到下一段數(shù)組進行二分查找。復雜度O(logn)
- 1 回答
- 0 關注
- 564 瀏覽
添加回答
舉報
0/150
提交
取消