阅读 49

学习算法第一天

预热

昨天半夜的一道题。

一个长度为N的数组,每个元素为0~9的数字,将其从大到小进行排序。

思路: 设定一个长度为10的数组,下标分别是0~9,遍历长度为N的数组,将其对应的下标元素+1,在输出的时候,从下标为9的开始遍历输出即可。

function Find(array){
  var box = new Array(10).fill(0);
  var arrayBox = [];
  array.forEach(function(value,index){
    box[value]++;
  })
  for(let j = box.length-1 ; j >= 0 ; j--){
    for(let i = 0 ; i < box[j] ; i++){
      arrayBox.push(j);
    }
  }
  return arrayBox;
}
复制代码

第一道题

在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

第一思路

解析

外层函数循环,第一个参数进行判断,如果第一个参数都大于目标数,那么不需要进行遍历,直接输出false,
如果小于目标数,对内层函数进行every循环,如果数字小于目标数,继续进行循环,
如果没有,判断是否相等,如果相等输出true,并结束循环,
如果大于就退出本次内层循环。

function Find(target, array)
{
    var have = false;
    array.forEach(function(value,index){
        //如果第一个数大于目标数,就返回false
        if(have == true || value[0] > target){
            return false;
        //第一个数不大于目标数,进入第二层循环
        } else {
            //如果里面的数小于目标数,就循环,如果大于目标数,就退出循环,如果等于也退出循环
            value.every(function(v,i){
                if(v < target){
                    return true;
                }else{
                    if(v == target){
                        have = true;
                    }
                    return false;
                }
            })
        }
    })
    return have;
}
复制代码

估计复杂度

空间复杂度是1,时间复杂度是M×N

第二思路

解析

将二维数组弄成棋盘,外层为排,内层为列。

可以看出来,左上角是最小数,右下角是最大数,那么我们从右上角进行,如果目标数比右上角的数大,那么向下走,如果比右上角的数小,就往左走。最坏的结果,是走到左下角。

  1. 首先注意判断边界:
  2. 跳出循环的条件: 2.1 首先到达左下角就说明,没有这个变量,需要跳出。 2.2 在循环中找到这个变量相等的情况,需要跳出。
function Find(target, array)
{
  //确定右上角起点坐标array[i][j] = array[0][array[0].length -1]
    //横排变量
    var i = 0;
    //竖排变量
    var j = array[0].length -1;
    //循环进行判断
    while(true){
        //判断边界,如果超出了左下角就退出循环并且返回false
        if(i >= array.length || j < 0){
            return false
        }
        //如果没有超出边界,就判断是否相等,如果相等直接跳出循环并且返回true
        if(target == array[i][j]){
            return true
        }
        //如果没有达到跳出循环条件,那么判断是该往下走还是往左走
        if(target > array[i][j]){
            i++;
        }else{
            j--;
        }
    }
}
复制代码

评估复杂度

空间复杂度是O1,时间复杂度是M+N

关注下面的标签,发现更多相似文章
评论