Problem
Key Idea
์ด์งํ์์ผ๋ก \(nums[m]\) ๊ฐ๊ณผ ์ ์์ ๊ฐ์ ๋น๊ตํด์ค๋ค.
- \(nums[m-1] \gt nums[m]\) ์ด๋ฉด:
index \(m\) ์ผ์ชฝ์ \(peak\)๊ฐ ์กด์ฌ.r <- m;
- \(nums[m] \lt nums[m+1]\) ์ด๋ฉด:
index \(m\) ์ค๋ฅธ์ชฝ์ \(peak\)๊ฐ ์กด์ฌ.l <- m+1;
- ๋๋ค ์๋๋ฉด:
index \(m\) ์์ฒด๊ฐ \(peak\).
return m;
Implementation
/**
* written: 2021. 12. 29. Wed. 16:05:01 [UTC+9]
* jooncco์ mac์์.
**/
typedef vector<int> vi;
class Solution {
public:
int findPeakElement(vi &nums) {
int n= nums.size();
// nums[-1]๊ณผ nums[n]์ด -โ ์ด๋ฏ๋ก size๊ฐ 1์ด๋ฉด ์์ฒด๊ฐ peak
if (n == 1) return 0;
int l= 0, r= n-1;
while (l < r) {
int m= l+(r-l)/2;
if (m > 0 && nums[m] < nums[m-1]) r= m;
else if (m < n-1 && nums[m] < nums[m+1]) l= m+1;
else return m; // peak๋ฅผ ์ฐพ์์ผ๋ ๋ฐ๋ก return.
}
// l == peak index
return l;
}
};
- Time: \(O(\log n)\)
Leave a comment