学习算法第一天

预热——桶排序起始

昨天半夜的一道题。

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

桶排序1.png

思路：
设定一个长度为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

第二思路

解析

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

棋盘.png

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

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