LeetCode题练习与总结：有序矩阵中第 K 小的元素--378

一、题目描述

给你一个 n x n 矩阵 matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
请注意，它是 排序后 的第 k 小元素，而不是第 k 个 不同 的元素。

你必须找到一个内存复杂度优于 O(n^2) 的解决方案。

示例 1：

输入：matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
输出：13
解释：矩阵中的元素为 [1,5,9,10,11,12,13,13,15]，第 8 小元素是 13

示例 2：

输入：matrix = [[-5]], k = 1
输出：-5

提示：

• n == matrix.length
• n == matrix[i].length
• 1 <= n <= 300
• -10^9 <= matrix[i][j] <= 10^9
• 题目数据 保证 matrix 中的所有行和列都按 非递减顺序 排列
• 1 <= k <= n^2

二、解题思路

由于矩阵的每一行和每一列都是有序的，我们可以使用二分查找的方法来找到第 k 小的元素。具体步骤如下：

1. 设置两个指针 left 和 right，分别指向矩阵中的最小值和最大值，即 matrix[0][0] 和 matrix[n-1][n-1]。
2. 计算中间值 mid = (left + right) / 2。
3. 统计矩阵中小于等于 mid 的元素个数 count。
4. 如果 count 小于 k，说明第 k 小的元素在 mid 的右侧，更新 left = mid + 1。
5. 如果 count 大于等于 k，说明第 k 小的元素在 mid 的左侧或等于 mid，更新 right = mid。
6. 重复步骤 2-5，直到 left 等于 right，此时的 left（或 right）即为第 k 小的元素。

三、具体代码

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        int left = matrix[0][0];
        int right = matrix[n - 1][n - 1];
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            int count = 0;
            int j = n - 1;
            
            // 统计小于等于 mid 的元素个数
            for (int i = 0; i < n; i++) {
                while (j >= 0 && matrix[i][j] > mid) {
                    j--;
                }
                count += (j + 1);
            }
            
            if (count < k) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return left;
    }
}

四、时间复杂度和空间复杂度

1. 时间复杂度

• 在 while 循环中，left 和 right 之间的距离在每次迭代后至少减少一半，因为 mid 是通过取 (left + right) / 2 计算得到的。这意味着循环会执行 O(log(max - min)) 次，其中 max 是矩阵中的最大值，min 是矩阵中的最小值。

• 在每次 while 循环中，我们执行了一个嵌套循环，它遍历矩阵的每一行，并且对于每一行，我们使用一个指针 j 来找到小于等于 mid 的元素个数。这个操作的时间复杂度是 O(n)，因为对于每一行，指针 j 最多从列的末尾移动到开头。

由于这两个操作是嵌套的，我们需要将它们的时间复杂度相乘。因此，总的时间复杂度是 O(n * log(max - min))。

2. 空间复杂度

• 我们只使用了常数个额外空间，即 left、right、mid、count、j 和循环变量 i。这些变量的大小不随输入矩阵的大小而变化。

• 我们没有使用任何额外的数据结构，如数组或集合，来存储中间结果。

因此，空间复杂度是 O(1)，表示算法使用了固定的额外空间。

五、总结知识点

• 二分查找算法：

  • 使用二分查找来寻找第 k 小的元素，通过不断缩小搜索范围来提高查找效率。

• 循环和条件判断：

  • 使用 while 循环来迭代二分查找过程，直到找到第 k 小的元素。
  • 使用 if-else 语句来判断当前统计的元素个数是否小于 k，从而决定如何调整搜索范围。

• 矩阵操作：

  • 理解矩阵的有序性质，并利用这一性质来优化查找过程。
  • 使用嵌套循环遍历矩阵的行和列。

• 指针或索引操作：

  • 使用变量 j 作为列索引，通过减小 j 的值来找到每行中小于等于 mid 的元素个数。

• 数学运算：

  • 计算中间值 mid 时，使用 (left + right) / 2 防止整数溢出。
  • 使用 count += (j + 1) 来累加每行中小于等于 mid 的元素个数。

• 边界条件处理：

  • 确保在 while 循环中 left 总是小于 right。
  • 在计算 mid 时，确保 mid 在 left 和 right 之间。

• 函数定义和返回值：

  • 定义了一个 kthSmallest 方法，接收一个二维整数数组和一个整数 k 作为参数，并返回一个整数结果。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。