刷题笔记:力扣第73、74题（二维矩阵）

力扣第73题-矩阵置零1.拿到题目后第一时间想到应该先遍历一遍矩阵分别使用一个行标记数组和一个列标记数组来标记哪里有0然后进行置零操作但题目要求使用原地算法即不开辟新的数组、直接在原矩阵上进行操作。2.那么就可以使用矩阵自身来记录哪一行哪一列有0。将矩阵第一行第一列作为标记数组遍历完一遍矩阵后在第一行第一列进行标记之后根据标记进行矩阵置零操作。在此之前需要先确认第一行和第一列自身有没有0如果有0的话需要再矩阵置零操作结束后单独将该行/列置零。完整代码如下1. /** 2. * 矩阵置零O(1) 额外空间 标准原地算法 3. * 若矩阵中某个元素为 0则将其所在的行和列全部置为 0 4. * 不能使用额外的数组存储标记只能用矩阵本身 少量变量 5. */ 6. void setZeroes(int** matrix, int matrixSize, int* matrixColSize) { 7. // 矩阵的行数和列数 8. int rowMax matrixSize; 9. int colMax *matrixColSize; 10. 11. // 两个标记变量记录【第一行】和【第一列】本身是否含有 0 12. int isRow0 0; // 第一行是否有 0 13. int isCol0 0; // 第一列是否有 0 14. 15. // 步骤1检查第一列有没有 0 16. for (int i 0; i rowMax; i){ 17. if (matrix[i][0] 0){ 18. isCol0 1; 19. break; 20. } 21. } 22. 23. // 步骤2检查第一行有没有 0 24. for (int i 0; i colMax; i){ 25. if (matrix[0][i] 0){ 26. isRow0 1; 27. break; 28. } 29. } 30. 31. // 步骤3用第一行 第一列做标记 32. // 遍历从 (1,1) 开始的区域不破坏第一行/第一列的标记 33. for (int i 1; i rowMax; i){ 34. for (int j 1; j colMax; j){ 35. // 如果当前位置是 0 36. if (matrix[i][j] 0){ 37. matrix[i][0] 0; // 标记第 i 行需要置零 38. matrix[0][j] 0; // 标记第 j 列需要置零 39. } 40. } 41. } 42. 43. // 步骤4根据标记置零 44. // 遍历非首行、非首列区域 45. for (int i 1; i rowMax; i){ 46. for (int j 1; j colMax; j){ 47. // 如果这一行 或 这一列被标记过就把当前位置置 0 48. if (matrix[i][0] 0 || matrix[0][j] 0){ 49. matrix[i][j] 0; 50. } 51. } 52. } 53. 54. // 步骤5最后处理第一行 55. // 如果第一行原本就有 0把整行置零 56. if (isRow0){ 57. for (int i 0; i colMax; i){ 58. matrix[0][i] 0; 59. } 60. } 61. 62. // 步骤6最后处理第一列 63. // 如果第一列原本就有 0把整列置零 64. if (isCol0){ 65. for (int i 0; i rowMax; i){ 66. matrix[i][0] 0; 67. } 68. } 69. 70. return; 71. }该算法的时间复杂度为O(rowMax × colMax)遍历了矩阵四次空间复杂度为O(1)均已是最优解。力扣第74题-搜索二维矩阵1.因为给定的二维矩阵已经按照升序排列所以初步思路为先找到目标值可能在的行然后遍历该行寻找目标值。完整代码如下1. bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target) { 2. int m matrixSize; // 矩阵行数 3. int n *matrixColSize; // 矩阵列数 4. int row; // 用来存储 target 最终所在的行号 5. 6. // 边界特判 7. // 如果矩阵第一个数就比 target 大直接返回 false整个矩阵都比它大 8. if (matrix[0][0] target){ 9. return false; 10. } 11. 12. // 第一步确定 target 在哪一行 13. // 遍历每一行的行首元素 matrix[row][0] 14. for (row 0; row m; row){ 15. // 如果行首直接等于 target直接找到返回 true 16. if (matrix[row][0] target){ 17. return true; 18. } 19. // 如果当前行首 target说明 target 一定在上一行 20. if (matrix[row][0] target){ 21. row--; // 回到上一行 22. break; // 退出循环已经找到目标行 23. } 24. } 25. 26. // 处理边界target 在最后一行 27. // 如果循环正常结束没有触发 break说明 target 在最后一行 28. if (row m){ 29. row m - 1; 30. } 31. 32. // 第二步在确定的行里线性查找 target 33. for (int i 0; i n; i){ 34. if (matrix[row][i] target){ 35. return true; 36. } 37. } 38. 39. // 这一行里也没找到说明矩阵里没有 target 40. return false; 41. }该算法的时间复杂度为O(m n)空间复杂度为O(1)已是比较优秀的解法。2.在前几次提交的过程中总是报错总结出有如下几个特殊情况需要注意①在一开始确定行数的时候目标值可能直接就等于该行第一个值可以直接输出true并且要注意for循环条件一定是大于而非大于等于因为后面会进行row--操作否则会找错行。②如果目标值小于第一行第一个值那么需要特殊处理直接输出false否则row--会导致数组越界。③如果遍历到最后一行都找不到大于目标值的值那么目标值只可能出现在最后一行而此时row m已经越界需要让row m – 1。3.因为矩阵已排好序可以考虑使用两次二分来寻找目标值第一次寻找可能在的行第二次找该行内有没有该值。完整代码如下1. bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target) { 2. int m matrixSize; // 矩阵总行数 3. int n *matrixColSize; // 矩阵总列数 4. 5. // 第一次二分查找定位 target 所在的行 6. int i 0, j m - 1, mid 0; // i行上界j行下界mid记录中间行初始化0防止越界 7. while (i j) { 8. mid (i j) / 2; // 计算中间行 9. 10. // 情况1当前行的最大值 target → target一定在更下面的行 11. if (matrix[mid][n - 1] target) { 12. i mid 1; 13. } 14. // 情况2当前行的最小值 target → target一定在更上面的行 15. else if (matrix[mid][0] target) { 16. j mid - 1; 17. } 18. // 情况3matrix[mid][0] ≤ target ≤ matrix[mid][n-1] 19. // → 说明 target 就在 mid 这一行直接退出循环 20. else { 21. break; 22. } 23. } 24. 25. // 退出循环后mid 就是我们找到的目标行 26. int row mid; 27. 28. // 第二次二分查找在确定的行里找 target 29. i 0, j n - 1; // 重置二分范围当前行的第0列 ~ 最后一列 30. while (i j) { 31. mid (i j) / 2; // 计算当前行中间列 32. 33. // 中间值 目标 → 去右边找 34. if (matrix[row][mid] target) { 35. i mid 1; 36. } 37. // 中间值 目标 → 去左边找 38. else if (matrix[row][mid] target) { 39. j mid - 1; 40. } 41. // 找到目标 → 直接返回 true 42. else { 43. return true; 44. } 45. } 46. 47. // 整行都找完了没找到 → 返回 false 48. return false; 49. }该算法的时间复杂度为O(log m log n)空间复杂度为O(1)效率已经非常高了。4.在本题使用二分的时候犯了一个错误while循环的条件应该是i j而不是i j。二分查找的循环条件必须是左指针小于等于右指针否则就会漏掉左右指针重合的情况5.ai给了我一个更加简便的二分算法代码1. bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target) { 2. int m matrixSize; // 矩阵行数 3. int n *matrixColSize; // 矩阵列数 4. 5. // 把整个矩阵 拉直 成一个 从 0 到 m*n-1 的有序一维数组 6. int left 0; 7. int right m * n - 1; 8. 9. // 标准二分查找 10. while (left right) { 11. // 求中间位置防止溢出 12. int mid left (right - left) / 2; 13. 14. // 核心魔法 15. // 一维下标 mid → 转回矩阵的 (行, 列) 16. // 行 mid / 列数 17. // 列 mid % 列数 18. int mid_value matrix[mid / n][mid % n]; 19. 20. // 找到目标返回 true 21. if (mid_value target) { 22. return true; 23. } 24. // 中间值 目标 → 去右边找 25. else if (mid_value target) { 26. left mid 1; 27. } 28. // 中间值 目标 → 去左边找 29. else { 30. right mid - 1; 31. } 32. } 33. 34. // 没找到 35. return false; 36. }该算法将二维矩阵拉伸成一个从0到m * n – 1的有序一维数组用以下公式来进行行列计算1. 行 mid / n 2. 列 mid % n这样就可以只进行一次二分查找就能找到目标值十分优雅。