剑 04: I - 二维数组中的查找

题目

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

示例

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

解析

Method Me
思路：数组扁平化并去重，判断其中是否存在目标整数

var findTargetNum = function (arr, num) {
  arr = [...new Set(arr.join('').split(',').map(item => +item))]
  return arr.findIndex(item => item === num) !== -1
}

Method 1 - 双层遍历

var findNumberIn2DArray = function(matrix, target) {
    for(let i= 0; i< matrix.length; i++){
            for(let j= 0; j< matrix[i].length; j++){
                if(matrix[i][j] === target){
                    return true
                }
    }
    }
    return false
};

Method 2 - 二分查找

var findNumberIn2DArray = function(matrix, target) {
    var row = matrix.length;
    if(row === 0 ) return false;
    var col = matrix[0].length;
    var x = row - 1;
    var y = 0;
    while( x >= 0 && x < row && y >= 0 && y < col ){
        if(matrix[x][y] === target) return true;
        else if(matrix[x][y] < target) y ++;
        else if(matrix[x][y] > target) x --;
    }
    return false
};