数组

[TOC]

1.二维数组中的查找

1.1 题目

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

时间限制：1秒 空间限制：32768

1.2 题解

1.2.1 无脑写法

• flat()

function Find(target, array)
{
    if(array.flat(1).indexOf(target) + 1) {
        return true
    }else{
        return false;
    }
}
// 请检查是否存在语法错误或者数组越界非法访问等情况
// 22ms 9384k
// flat()存在兼容问题

• toString()

function Find(target, array)
{
  return (arr.toString().split(',').find(n => n==target)) ? true:false;
}

1.2.2 二分查找法

• 对每一行的数组都进行二分查找

// 114ms 9060k
function Find(target, array)
{
    for (let i = 0; i < array.length;i++ ) {
        let low = 0;
        let high = array[i].length - 1;
        while (low <= high) {
            let mid = Math.floor((low + high) / 2);
            if (target == array[i][mid]) {
                return true;
            } else if (target < array[i][mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
    }
    return false;
}

1.2.3 规律法

1 2 4 8 10

3 8 9 12 13

5 9 11 13 16

7 10 13 15 19

从右上或左上角找，每次找都能去除一行或列

// 94ms 9132k
function Find(target, array)
{
    let row = 0,
        col = array[0].length-1;
    while (row <= array.length-1 && col >= 0) {
        if (target == array[row][col]) {
            return true;
        } else if (target < array[row][col]) {
            col--;
        } else {
            row++;
        }
    }
    return false;
}

// 84ms 8020k
function Find(target, array)
{ 
    let lenX = array[0].length-1,lenY = array.length-1;
    for (let i = 0,j = lenX;i <= lenY && j >= 0;) {
        if (target == array[i][j]) {
            return true;
        } else if (target < array[i][j]) {
            j--;
        } else {
            i++;
        }
    }
    return false;
}

1.2.4 二分规律法

就平均情况而言，每次查找行数和列数都会减少一半。

参考链接：https://www.jianshu.com/p/4e48ed2676ef (opens new window)

// 暂且知道思路就好，要考虑的情况有点多
// 要递归