日期:2021年4月8日

在二维数组中查找指定值

一.数组

数组是一种最简单的数据结构,在内存中占据一块连续的存储结构,可以通过数组下标进行访问。对比链表,其具有访问速度快,时间效率 高的特点。但是数组需要预先在内存中分配存储空间,因此数组的空间效率不是很好,经常会有空间没有得到充分的利用。

二.二维数组中的查找

在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。 例如,有如下数组a,需要在里面寻找7。

1,3,6,7
3,6,8,10
5,9,10,12

很多人,按照惯性思维会直接从下标0开始进行比较,将a[0][0]与7进行比较,a[0][0]小于7,所以可能的值在左下方和右上方,继续比较a[1][1]a[1][1]小于7,得到7可能存在于左下方和右上方。每次比较都会出现两个可能的区域左下方和右上方,这样看问题会变得越来越复杂。

二维数组中的查找

所以不妨换一个角度,从右上角出发,每次比较右上角的数字,来缩小比较范围,例如我们要在a中寻找5,首先将7与5比较,7大于5,所以7所在的列不可能存在5。所以踢出当前列。在将6与5比较,6大于5,再踢出6所在的列。继续比较3和5,因为3小于5,所以踢出3所在的行。这样每比较一次,会缩小查找的范围,直到找到5。

代码:

/**
 * 在二维数组中查找指定值
 * @param arr 二维数组
 * @param value 需要查找的值
 * @returns 如果存在返回索引值, 不存在返回{i: -1, j: -1}
 */
const includes = (arr: number[][], value: number): boolean => {
    // 检查数组长度
    if (arr.length === 0) {
        return false;
    }
    if (arr[0].length === 0) {
        return false;
    }
    // 从数组右上角进行比较
    let i = 0, j = arr[0].length - 1;
    while(i < arr.length && j > 0) {
        if (arr[i][j] === value) {
            return true;
        }
        if (arr[i][j] < value) {
            i++;
        }
        if (arr[i][j] > value) {
            j--;
        }
    }
    return false;
};

测试:

const arr1: number[][] = [[]];
const arr2: number[][] = [[1, 3, 5, 7], [3, 6, 8, 10], [5, 9, 10, 12], [7, 12, 14, 20]];
const arr3: number[][] = [[1, 3, 5, 7], [3, 6, 8, 10]];
console.log(includes(arr1, 0)); // false
console.log(includes(arr2, -1)); // false
console.log(includes(arr2, 7)); // true
console.log(includes(arr2, 5)); // true
console.log(includes(arr2, 4)); // false
console.log(includes(arr3, -1)); // false
console.log(includes(arr3, 7)); // true
console.log(includes(arr3, 5)); // true
console.log(includes(arr3, 4)); // false

同样我们也可以从左下角进行出发,当比较的数字大于目标值时,踢出当前行,小于目标值时踢出当前列,以此来缩小查找范围。

github地址

(完)

留言(0
发表评论
邮箱地址不会被公开。*表示必填项。
评论(支持部分html标签)*
姓名*
站点