写点什么

搜索二维矩阵②

用户头像
Memorys
关注
发布于: 3 小时前
搜索二维矩阵②

题目:

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性: 每行的元素从左到右升序排列。 每列的元素从上到下升序排列。


没有暴力破解法,挨个查太慢了。

因此主要用了两种方式搜索:

  1. 二分法

  2. 根据值的特性一步一步位移



package com.memorys.algorithm.year2021.month08;

/** * * @Description: * 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性: * * 每行的元素从左到右升序排列。 * 每列的元素从上到下升序排列。 * * 作者:力扣 (LeetCode) * 链接:https://leetcode-cn.com/leetbook/read/top-interview-questions/xmlwi1/ * * * @Date 2021-08-07 23:09 * @Description */public class SearchMatrix {
public static void main(String[] args) {
int [][] 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} }; int target = 31; boolean result1 = SearchMatrix1(matrix, target); System.out.println(result1);
boolean result2 = SearchMatrix2(matrix, target); System.out.println(result2);
}

/** * @CreateDate 2021-08-07 23:19 * @param matrix * @param target * @Description * 找到目标数,常用的算法就是2分法, * 因此,对每一行进行二分查找,一直到找出结果位置 * * 时间复杂度为O(m㏒n) * * @Return boolean */ public static boolean SearchMatrix1(int[][] matrix, int target){

for (int i = 0 ;i < matrix.length; i++) { int arr[] = matrix[i]; boolean result = binarySearch2(arr, target,0,arr.length - 1); if (result){ return result; } } return false; }
private static boolean binarySearch2(int[] arr, int target, int from, int to){ if (to < from){ return false; } if (to == from){ if (arr[to] == target){ return true; }else { return false; } } if (to - from == 1){ if(arr[to] == target || arr[from] == target){ return true; }else { return false; } }
int middle = from + (to - from)/2; if (arr[middle] == target){ return true; } if (arr[middle] > target){ return binarySearch2(arr,target,from,middle); } if (arr[middle] < target){ return binarySearch2(arr,target,middle,to); } return false; }


/** * @CreateDate 2021-08-08 10:02 * @param matrix * @param target * @Description : * 通过题目的描述可以看出,对于矩阵的某一个节点来说,、 * 左上角的肯定比它小,右下角的肯定比它大, * 但是左下角和右上角和它的大小关系是不确定的。 * * 因此不能用从中间查找的方法来查找,只能尽可能的缩小不确定的范围的个数。 * 不确定的在左下角以及右上角。 * 同时因为要判断大小,因此需要,比自己大的都在同一个方向,比自己小的在另外一部分方向。 * 因此坐上,右下不符合要求。 * 因此我们从最左下角或者最右上角开始找。 * 这里拿最左下角当做例子。 * 上边的都比自己小,右边的都比自己大。 * 因此目标值比自己大,那就往右找,目标值比自己小就往上找即可。 * * 时间复杂度为:O(m+n) * * @Return boolean */ public static boolean SearchMatrix2(int[][] matrix, int target){ int width = 0; int length = matrix.length - 1; while (matrix[length][width] != target){ int num = matrix[length][width]; if (matrix[length][width] == target){ return true; }
if (matrix[length][width] > target){ length = length - 1; if (length == -1){ return false; } }else if (matrix[length][width] < target){ width = width + 1; if (width == matrix[0].length){ return false; } } }
return true; }

}
复制代码


用户头像

Memorys

关注

还未添加个人签名 2018.08.13 加入

还未添加个人简介

评论

发布
暂无评论
搜索二维矩阵②