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