2022-10-10 08:40

LeetCode 劍指 Offer 04. 二維數(shù)組中的查找

@TOC

題目描述

?在一個(gè) n * m 的二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請(qǐng)完成一個(gè)高效的函數(shù)，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)，判斷數(shù)組中是否含有該整數(shù)。

示例：

[
?[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]
]

提示：

0 <= n <= 1000

0 <= m <= 1000

一、解題關(guān)鍵詞

有序

二、解題報(bào)告

1.思路分析

1. 可以暴力

2. 但是必須使用二分解決，二分有兩種

3. 行二分，列二分

4. 經(jīng)典的left right mid 判斷是否在該區(qū)間內(nèi)，返回index

2.時(shí)間復(fù)雜度

3.代碼示例

class Solution {
? ?public boolean findNumberIn2DArray(int[][] matrix, int target) {
? ? ? ?for(int[] row : matrix){
? ? ? ? ? ?int index = search(row,target);
? ? ? ? ? ?if(index >= 0){
? ? ? ? ? ? ? ?return true;
? ? ? ? ? ?}
? ? ? ?}
? ? ? ?return false;
? ?}
?//也可以使用Arrays.binarySerach（）d
? ?int search(int[] nums ,int target){
? ? ? ?int left = 0,right = nums.length - 1;
? ? ? ?while(left <= right){
? ? ? ? ? ?int mid = left +(right - left) / 2;
? ? ? ? ? ?int num = nums[mid];
? ? ? ? ? ?if(num == target){
? ? ? ? ? ? ? ?return mid;
? ? ? ? ? ?}else if(num > target){
? ? ? ? ? ? ? ?right = mid - 1;
? ? ? ? ? ?}else{
? ? ? ? ? ? ? ?left = mid + 1;
? ? ? ? ? ?}
? ? ? ?}
? ? ? ?return -1;
? ?}
}

代碼二：

class Solution {
? ?public boolean findNumberIn2DArray(int[][] matrix, int target) {
? ? ? ?int rowLen = matrix.length - 1;
? ? ? ?int colLen = 0;

? ? ? ?while(rowLen >= 0 && colLen < matrix[0].length){
? ? ? ? ? ?if(matrix[rowLen][colLen] > target){
? ? ? ? ? ? ? ?rowLen--;
? ? ? ? ? ?}else if(matrix[rowLen][colLen] < target){
? ? ? ? ? ? ? ?colLen ++;
? ? ? ? ? ?}else{
? ? ? ? ? ? ? ?return true;
? ? ? ? ? ?}
? ? ? ?}
? ? ? ?return false;
? ?}
}

4.知識(shí)點(diǎn)