欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页  >  IT编程

leetcode求峰值，js实现

程序员文章站 2022-04-30 19:52:07
原题： 最开始是照着提示的思路进行，中规中矩，用时64ms 然后想着优化，对着一个数组反复琢磨，发现一个规律： nums.length=0,1,2不谈，从nums.length>3开始，i=0，如果nums[i]>nums[i+1]，直接得出第一个峰值；如果nums[i]

原题：

leetcode求峰值，js实现

 

 

最开始是照着提示的思路进行，中规中矩，用时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，到此优化结束

上一篇： javascript应该嵌入到html中的什么位置

下一篇： Windows Mobile引路蜂地图开发示例：本地查询

推荐阅读