|
| 1 | +packagemedium; |
| 2 | + |
| 3 | +publicclassFindPeakElement { |
| 4 | + |
| 5 | +/** |
| 6 | + * On discuss, this post has very good explanation about an O(logn) solution: |
| 7 | + * https://discuss.leetcode.com/topic/29329/java-solution-and-explanation-using-invariants |
| 8 | + * |
| 9 | + * Basically, we need to keep this invariant: |
| 10 | + * nums[left] > nums[left-1], then we could return left as the result |
| 11 | + * or nums[right] > nums[right+1], then we could return right as the result |
| 12 | + */ |
| 13 | +publicstaticintfindPeakElement_Ologn(int[]nums) { |
| 14 | + |
| 15 | +if(nums ==null ||nums.length ==0)return0; |
| 16 | +intleft =0,right =nums.length-1; |
| 17 | +while(left+1 <right){ |
| 18 | +intmid =left + (right-left)/2; |
| 19 | +if(nums[mid] <nums[mid+1]){ |
| 20 | +left =mid; |
| 21 | + }else { |
| 22 | +right =mid; |
| 23 | + } |
| 24 | + } |
| 25 | +return (left ==nums.length-1 ||nums[left] >nums[left+1]) ?left :right; |
| 26 | + |
| 27 | + } |
| 28 | + |
| 29 | +/**My original O(n) solution.*/ |
| 30 | +publicstaticintfindPeakElement(int[]nums) { |
| 31 | +if(nums ==null ||nums.length ==0)return0; |
| 32 | +intn =nums.length,result =0; |
| 33 | +for(inti =0;i <n;i++){ |
| 34 | +if(i ==0 &&n >1 &&nums[i] >nums[i+1]){ |
| 35 | +result =i; |
| 36 | +break; |
| 37 | + }elseif(i ==n-1 &&i >0 &&nums[i] >nums[i-1]){ |
| 38 | +result =i; |
| 39 | +break; |
| 40 | + }elseif(i >0 &&i <n-1 &&nums[i] >nums[i-1] &&nums[i] >nums[i+1]){ |
| 41 | +result =i; |
| 42 | +break; |
| 43 | + } |
| 44 | + } |
| 45 | +returnresult; |
| 46 | + } |
| 47 | + |
| 48 | +publicstaticvoidmain(String...strings){ |
| 49 | +// int[] nums = new int[]{1,2}; |
| 50 | +// int[] nums = new int[]{1}; |
| 51 | +int[]nums =newint[]{1,2,3,1}; |
| 52 | +// System.out.println(findPeakElement(nums)); |
| 53 | +System.out.println(findPeakElement_Ologn(nums)); |
| 54 | + } |
| 55 | +} |