leetcode74：搜索二维矩阵

题目链接

leetcode

题目描述

给你一个满足下述两条属性的 m x n 整数矩阵：

• 每行中的整数从左到右按非严格递增顺序排列。
• 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

C++ 代码

#include <iostream>
#include <vector>
#include <iomanip> // 用于设置输出格式
using namespace std;

void printArray(const vector<vector<int>>& nums) {
    int width = 3; // 设置每个数字的宽度为3
    for (auto& row : nums) {
        for (auto& num : row) {
            // cout << num << " ";
            cout << setw(width) << num; // 设置宽度为3
        }
        cout << endl;
    }
}

/*
    从左下角（或右上角）开始查找
    
    时间复杂度：O(m+n)
        其中 m 和 n 分别是矩阵的行数和列数。
    空间复杂度：O(1)
*/
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) return false;

        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;
            else if (matrix[i][j] < target) i ++; // 该数偏小，向下移动
            else j --; // 该数偏大，向上移动
        }
        
        // 若 while 循环后没有找到，则 target 不存在
        return false;
    }
};

/*
    一次二分查找

    二维矩阵按行展开成一维数组，这个一维数组单调递增，可以直接二分。
    坐标映射：通过整除和取模运算得到二维数组的坐标。

    时间复杂度：O(logmn)
        其中 m 和 n 分别是矩阵的行数和列数。
    空间复杂度：O(1)
*/
class Solution_1 {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) return false;

        int m = matrix.size(), n = matrix[0].size();
        int l = 0, r = m * n - 1;
        while (l < r) {
            // int mid = l + r >> 1;
            // if (matrix[mid / n][mid % n] >= target) r = mid;
            // else l = mid + 1;
            int mid = (l + r) / 2, row = mid / n, col = mid % n;
            if (matrix[row][col] > target) r = mid;
            else if (matrix[row][col] < target) l = mid + 1;
            else if (matrix[row][col] == target) r = mid;
        }

        // 若 while 循环后没有找到，则 target 不存在
        return matrix[r / n][r % n] == target;
    }
};

int main() {
    Solution solution;
    vector<vector<int>> matrix = {
        {1, 3, 4, 5},
        {10, 11, 16, 20},
        {23, 30, 34, 60}
    };
    printArray(matrix);
    int target = 5;
    bool result = solution.searchMatrix(matrix, target);
    cout << "Target " << target << " is found in the matrix: " << (result ? "Yes" : "No") << endl;
    
    return 0;
}

Golang 代码

package main

import (
	"fmt"
)

/*
   二分查找（将二维矩阵视为一维数组）
       将二维矩阵视为一个一维数组，通过索引映射将一维索引转换为二维索引。
       使用标准二分查找算法，在一维数组中查找目标值。
       如果目标值等于中间元素，返回 true。
       如果目标值小于中间元素，调整右边界；如果目标值大于中间元素，调整左边界。
       如果查找结束仍未找到目标值，返回 false。

   时间复杂度：O(log(m*n))
       二维矩阵的大小为 m × n，将其视为一维数组后，数组长度为 m * n。
       二分查找的时间复杂度为 O(log(m*n))，即 O(logm + logn)。
   空间复杂度：O(1)
       仅使用了常数级别的额外空间，空间复杂度为 O(1)。
*/
// searchMatrix 返回目标值是否在二维矩阵中
func searchMatrix(matrix [][]int, target int) bool {
	if len(matrix) == 0 || len(matrix[0]) == 0 {
		return false
	}

	m, n := len(matrix), len(matrix[0])
	left, right := 0, m*n - 1

	for left <= right {
		mid := (left + right) / 2
		row, col := mid / n, mid % n

		if matrix[row][col] == target {
			return true
		} else if matrix[row][col] < target {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}

	return false
}

func main() {
	// 测试用例
	testCases := []struct {
		matrix   [][]int
		target   int
		expected bool
	}{
		{
			matrix:   [][]int{{1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 60}},
			target:   3,
			expected: true,
		},
		{
			matrix:   [][]int{{1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 60}},
			target:   13,
			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)
		}
	}
}