2. 二维数组中的查找

题目描述

给定一个二维数组,其每一行从左到右递增排序,从上到下也是递增排序。给定一个数,判断这个数是否在该二维数组中。

Consider the following matrix:
[
  [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]
]

Given target = 5, return true.
Given target = 20, return false.

解题思路

要求时间复杂度 O(M + N),空间复杂度 O(1)。其中 M 为行数,N 为 列数。

该二维数组中的一个数,小于它的数一定在其左边,大于它的数一定在其下边。因此,从右上角开始查找,就可以根据 target 和当前元素的大小关系来缩小查找区间,当前元素的查找区间为左下角的所有元素。

代码实现

java 代码

/**
 * 判断给定的Value值是否在二维数组中
 * @param arr 给定的二维数组
 * @param value 给定用来判断的值
 * @return 
 */
private boolean isInArr(int[][] arr, int value) {
    if (arr == null || arr.length == 0 || arr[0].length == 0) {
        return false;
    }
    //从左下角开始,如果value比当前位置的元素小,则向上一行(r--);如果value比当前位置元素大,则向右一列(c++)
    int r = arr.length - 1, c = 0;
    while (r >= 0 && c < arr[r].length) {
        if (arr[r][c] > value) {
            r--;
            continue;
        }
        if (arr[r][c] < value) {
            c++;
            continue;
        }
        if (arr[r][c] == value) {
            return true;
        }
    }
    return false;
}

public static void main(String[] args){
    int[][] array = {
            {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}
    };
    System.out.println(isInArr(array, 5));
    System.out.println(isInArr(array, 20));
}

Kotlin 代码

/**
 * 判断给定的Value值是否在二维数组中
 * @param array 给定的二维数组
 * @param value 给定用来判断的值
 * @return
 */
private fun isInArr(array: Array<Array<Int>>, value: Int): Boolean {
    if (array.isEmpty() || array[0].isEmpty()) {
        return false
    }
    var r = array.size - 1
    var c = 0;
    while (r >= 0 && c < array[r].size) {
        if (array[r][c] < value) {
            c++
            continue
        }
        if (array[r][c] > value) {
            r--
        }
        return true
    }
    return false
}

/**
 * 入口函数
 */
fun main(args: Array<String>) {
   val array = arrayOf(
    arrayOf(1, 4, 7, 11, 15),
    arrayOf(2, 5, 8, 12, 19),
    arrayOf(3, 6, 9, 16, 22),
    arrayOf(10, 13, 14, 17, 24),
    arrayOf(18, 21, 23, 26, 30)
    )
    println(isInArr(array, 5))
    println(isInArr(array, 20))
}

引用声明

该题目引用自
牛客网