Jamzen的技术博客
0%

LeetCode.搜索二维矩阵

发表于 分类于 Valine：

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：每行中的整数从左到右按升序排列。每行的第一个整数大于前一行的最后一个整数。

  1. 示例 1：
    输入：matrix = [ [1,3,5,7],[10,11,16,20],[23,30,34,50] ], target = 3
    输出：true
  2. 示例 2：
    输入：matrix = [ [1,3,5,7],[10,11,16,20],[23,30,34,50] ], target = 13
    输出：false
  3. 示例 3：
    输入：matrix = [], target = 0
    输出：false

二分查找：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
object SearchMatrix {
     def main(args: Array[String]): Unit = {
          val matrix = Array[Array[Int]](
               Array[Int](1, 3, 5, 7),
               Array[Int](10, 11, 16, 20),
               Array[Int](23, 30, 34, 50)
          )

          println(searchMatrix(matrix, 3))
          println(searchMatrix(matrix, 0))
          println(searchMatrix(matrix, 1))
          println(searchMatrix(matrix, 50))

          val matrix2 = Array[Array[Int]](
               Array[Int](1, 3, 5, 7)
          )

          println(searchMatrix(matrix2, 0))
          println(searchMatrix(matrix2, 1))
          println(searchMatrix(matrix2, 3))
          println(searchMatrix(matrix2, 7))
          println(searchMatrix(matrix2, 9))
     }

     /**
      * 二分查找，时间复杂度O(log(mn)),空间复杂度O(1)
      */
     def searchMatrix(matrix: Array[Array[Int]], target: Int): Boolean = {
          val m = matrix.length
          if (m == 0) return false
          val n = matrix(0).length

          var l = (0, 0)
          var r = (m - 1, n - 1)

          while (l._1 * n + l._2 + 1 <= r._1 * n + r._2 + 1) {
               val middle = calM(l, r, n, 0)
               if (matrix(middle._1)(middle._2) < target) {
                    l = calM(l, r, n, 2)
               } else if (matrix(middle._1)(middle._2) > target) {
                    r = calM(l, r, n, 1)
               } else {
                    return true
               }
          }

          false
     }

     def calM(l: (Int, Int), r: (Int, Int), n: Int, flag: Int): (Int, Int) = {
          val s = l._1 * n + l._2
          val e = r._1 * n + r._2
          var middle = 0
          if (flag == 0) {
               middle = (s + e) / 2
          } else if (flag == 1) {
               middle = (s + e) / 2 - 1
          } else {
               middle = (s + e) / 2 + 1
          }

          (middle / n, middle % n)
     }
}