leetcode240：搜索二维矩阵II

题目链接

leetcode

题目描述

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

  • 每行的元素从左到右升序排列。
  • 每列的元素从上到下升序排列。

C++ 代码

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <iostream>
#include <vector>
using namespace std;

/*
    直接遍历整个矩阵 matrix，判断 target 是否出现即可。

    时间复杂度：O(m * n)
        其中 m 为矩阵的行数，n 为矩阵的列数。
    空间复杂度：O(1)
        只使用了固定的几个变量。
*/
class Solution_0 {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        for (const auto& row : matrix) {
            for (int element: row) {
                if (element == target) {
                    return true;
                }
            }
        }
        return false;
    }
};

/*
    整个矩阵按行展开成一个一维数组。
    由于这个一维数组单调递增，所以可以二分。

    时间复杂度：O(m * logn)
        其中 m 为矩阵的行数，n 为矩阵的列数。
        对一行使用二分查找的时间复杂度为 O(logn)，最多需要进行 m 次二分查找。
    空间复杂度：O(1)
        只使用了固定的几个变量。
*/
class Solution_1 {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        // for (const auto& row : matrix) {
        //     auto it = lower_bound(row.begin(), row.end(), target);
        //     if (it != row.end() && *it == target) {
        //         return true;
        //     }
        // }
        for (int i = 0; i < m; i ++) {
            if (matrix[i][0] > target) break;
            if (matrix[i][n - 1] < target) continue;

            int col = binarySearch(matrix[i], target);
            if (col != -1) return true;
        }

        return false;
    }

    int binarySearch(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        while (l <= r) {
            int mid = l + r >> 1;
            if (nums[mid] == target) return mid;
            else if (nums[mid] < target) l = mid + 1;
            else r = mid - 1;
        }

        return -1;
    }
};

/*
    从右上角（左下角）开始找

    时间复杂度：O(m + n)
        其中 m 为矩阵的行数，n 为矩阵的列数。
    空间复杂度：O(1)
        只使用了固定的几个变量。
*/
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        int i = 0, j = n - 1;
        while (i < m && j >= 0) {
            if (matrix[i][j] == target) return true;
            if (matrix[i][j] > target) j --; // 需要小一点，往左移动
            else i ++; // 需要大一点，往下移动
        }

        // while 循环中没有找到，则 target 不存在
        return false;
    }
};

int main() {
    Solution solution;
    vector<vector<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 = 5;
    bool result = solution.searchMatrix(matrix, target);

    cout << "Target found: " << (result ? "Yes" : "No") << endl;

    return 0;
}

Golang 代码

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
package main

import "fmt"

/*
   基本思路：
       使用了二分查找来在每一行中查找目标值。
       对于每一行，将其视为一个有序的数组，并使用二分查找来确定目标值是否存在。

   时间复杂度：O(m*logn)
       其中 m 为矩阵的行数，n 为矩阵的列数。
       对每一行进行二分查找，因此时间复杂度为 O(m*logn)。
   空间复杂度：O(1)
       只使用了固定的几个变量。
*/
func searchMatrix_0(matrix [][]int, target int) bool {
    rows, cols := len(matrix), len(matrix[0])
	for row := 0; row < rows; row ++ {
		left, right := 0, cols - 1
		for left <= right {
			mid := left + (right - left)/2
			if matrix[row][mid] == target {
				return true
			} else if matrix[row][mid] < target {
				left = mid + 1
			} else {
				right = mid - 1
			}
		}
	}

	return false
}

/*
   基本思路：
       从矩阵的右上角开始，按照从右到左、从上到下的顺序进行搜索。
       若找到目标值，则返回 true；
       否则，返回 false。

   时间复杂度：O(m + n)
       其中 m 为矩阵的行数，n 为矩阵的列数。
   空间复杂度：O(1)
       只使用了固定的几个变量。
*/
func searchMatrix(matrix [][]int, target int) bool {
	rows, cols := len(matrix), len(matrix[0])
	x, y := 0, cols - 1

	for x < rows && y >= 0 {
		if matrix[x][y] == target {
			return true
		} else if matrix[x][y] > target {
			y --
		} else {
			x ++
		}
	}
    
	return false
}

func main() {
	// 测试用例
	testCases := []struct {
		matrix   [][]int
		target   int
		expected bool
	}{
		{
			matrix: [][]int{
				{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},
			},
			target:   5,
			expected: true,
		},
		{
			matrix: [][]int{
				{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},
			},
			target:   20,
			expected: false,
		},
	}

	for i, tc := range testCases {
		result := searchMatrix(tc.matrix, tc.target)
		fmt.Printf("Test Case %d, Input: matrix = %v, target = %d\n", i+1, tc.matrix, tc.target)
		if result == tc.expected {
			fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, result)
		} else {
			fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %v)\n", i+1, result, tc.expected)
		}
	}
}
#leetcode
leetcode240：搜索二维矩阵II
https://lcf163.github.io/2024/05/03/leetcode240：搜索二维矩阵II/
作者
乘风的小站
发布于
2024年5月3日
许可协议