二维数组中的查找

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))
    }

引用声明

该题目引用自
牛客网