题目链接

题目描述

image.png
image.png

思路：

思路一：暴力破解
思路二：对每一行进行二分查找

  1. public boolean searchMatrix(int[][] matrix, int target) {
  2.     for (int[] ints : matrix) {
  3.         if (search(ints, target) != -1) {
  4.             return true;
  5.         }
  6.     }
  7.     return false;
  8. }
  10. /**
  11.  * 二分查找
  12.  *
  13.  * @param nums   nums
  14.  * @param target 目标元素
  15.  * @return 最终位置，没有返回 -1
  16.  */
  17. public int search(int[] nums, int target) {
  18.     int low = 0;
  19.     int high = nums.length - 1;
  21.     while (low <= high) {
  22.         int mid = (high - low) / 2 + low;
  23.         int num = nums[mid];
  24.         if (num == target) {
  25.             return mid;
  26.         } else if (nums[mid] > target) {
  27.             high = mid - 1;
  28.         } else if (nums[mid] < target) {
  29.             low = mid + 1;
  30.         }
  31.     }
  33.     return -1;
  34. }

思路三：Z 字查找
image.png
建议直接代码调试，秒懂

  1. public boolean searchMatrix(int[][] matrix, int target) {
  2.     int m = matrix.length;
  3.     int n = matrix[0].length;
  4.     int x = 0;
  5.     int y = n - 1;
  6.     // 小于范围才进行查找
  7.     while (x < m && y >= 0) {
  8.         if (matrix[x][y] == target) {
  9.             return true;
  10.         }
  11.         if (matrix[x][y] > target) {
  12.             --y;
  13.         } else {
  14.             ++x;
  15.         }
  16.     }
  17.     return false;
  18. }

这个思路也可以看成是对角搜索
image.png