原题:
最开始是照着提示的思路进行,中规中矩,用时64ms
/** * @param {number[]} nums * @return {number} */ var findPeakElement = function(nums) { let i=0; let j=nums.length-1; let nums[-1]=nums[0]-1; let nums[nums.length]=nums[nums.length-1]-1; if(j===0) return 0; else if(j===1) return nums[0]>nums[1] ? 0 : 1; else{ while(i<=j){ if(nums[i]>nums[i-1] && nums[i]>nums[i+1]){ return i; }else{ i++ } if(nums[j]>nums[j-1] && nums[j]>nums[j+1]){ return j; }else{ j--; } } } };
然后想着优化,对着一个数组反复琢磨,发现一个规律:
nums.length=0,1,2不谈,从nums.length>3开始,i=0,如果nums[i]>nums[i+1],直接得出第一个峰值;如果nums[i]<nums[i+1]则说明nums[i]不是峰值,而这恰恰就是关键,既然nums[i]不是峰值,必然有nums[i+1]>nums[i],那么当i=2的时候,就可以省略一次比较了,优化如下:
/** * @param {number[]} nums * @return {number} */ var findPeakElement = function(nums) { let i=0; let j=nums.length-1; if(j===0) return 0; else if(j===1) return nums[0]>nums[1] ? 0 : 1; else{ while(i<=j){ if(nums[i]>nums[i+1]){ return i; }else{ i++ } if(nums[j]>nums[j-1]){ return j; }else{ j--; } } } };
不错了,用时60ms,那么还可以继续优化吗?
当然可以,在运行过程中,碰到return就直接结束了,那么不需要那么多的if-else
/** * @param {number[]} nums * @return {number} */ var findPeakElement = function(nums) { let i=0; let j=nums.length-1; if(j===0) return 0; if(j===1) return nums[0]>nums[1] ? 0 : 1; while(i<=j){ if(nums[i]>nums[i+1]){ return i; } else{ if(nums[j]>nums[j-1]){ return j; } i++; j--; } } };
用时52ms,到此优化结束
内容来源于网络如有侵权请私信删除
- 还没有人评论,欢迎说说您的想法!