C/C++教程

Leetcode.有序矩阵中第 K 小的元素

本文主要是介绍Leetcode.有序矩阵中第 K 小的元素,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

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

示例 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

解题思路:

  1. 找出二维矩阵中最小的数 left,最大的数 right,那么第 k 小的数必定在 left ~ right 之间
  2. mid=(left+right) / 2;在二维矩阵中寻找小于等于 midmid 的元素个数 count
  3. 若这个 count小于 k,表明第 k 小的数在右半部分且不包含 mid,即 left=mid+1, right=right,又保证了第 k 小的数在left ~ right之间
  4. 若这个 count大于 k,表明第 k 小的数在左半部分且可能包含 mid,即 left=left, right=mid,又保证了第 k 小的数在 left~right之间
  5. 因为每次循环中都保证了第 k 小的数在 left ~ right 之间,当 left==right 时,第 k 小的数即被找出,等于 right

解题代码:

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) >> 1);
            if (check(matrix, mid, k, n)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    public boolean check(int[][] matrix, int mid, int k, int n) {
        int i = n - 1;
        int j = 0;
        int num = 0;
        while (i >= 0 && j < n) {
            if (matrix[i][j] <= mid) {
                num += i + 1;
                j++;
            } else {
                i--;
            }
        }
        return num >= k;
    }
}
这篇关于Leetcode.有序矩阵中第 K 小的元素的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!