---

矩阵相关

1. 旋转矩阵

题目描述： 给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
题解思路： 先将矩阵上下翻转，然后对矩阵进行对角线翻转。
题解代码：

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        // 使用两次反转，先上下翻转，后对角线翻转
        // 上下翻转
        for (int i = 0; i < (n / 2); i++) {
            for (int j = 0; j < n; j++) {
                swap(matrix[i][j], matrix[n-i-1][j]);
            }
        }

        // 对角线翻转
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                swap(matrix[i][j], matrix[j][i]);
            }
        }
    }
};

关键结论：对于矩阵中的元素 $\text{matrix}[\text{row}][\text{col}]$，在旋转后，它的新位置为 ${\text{matrix}}_{\text{new}}[\text{col}][n-\text{row}-1]$ 。

---

2. 搜索二维矩阵

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

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。
  
  题解思路： 由于每一行都是单调递增的，因此可以逐行使用二分查找，这样就可以将时间复杂度控制在$O(nlogm)$之内。
  题解代码：

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        for(const auto&  row : matrix){
            auto it = lower_bound(row.begin(),row.end(),target);
            if( it != row.end() && *it == target){
                return true;
            }
        }
        return false;
    }
};

注意，需要先判断it != row.end()，再判断*it == target，否则，判断*it == target会不合法，导致未定义行为（Undefined Behavior, UB）

关于 lower_bound(StartIterator, EndIterator, Value)方法的使用：
StartIterator：范围开始的迭代器。
EndIterator：范围结束的迭代器。
Value：需要查找的值。

---