leetcode做题记录 —— kth-smallest-element-in-a-sorted-matrix

kth-smallest-element-in-a-sorted-matrix

Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

Example:

1.matrix = [
2.   [ 1,  5,  9],
3.   [10, 11, 13],
4.   [12, 13, 15]
5.],
6.k = 8,
7.return 13.

Note: 
You may assume k is always valid, 1 ≤ k ≤ n2.

Kth Smallest Element in a Sorted Matrix

输入一个矩阵和一个整数 k ，求矩阵中第 k 小的数。

解法一

因为行和列都是有序的，所以第 k 小的数的上界可以算出来，然后把上界之内的所有数放进数组里，排序后输出 k 位。

1.//Javascript
2.var kthSmallest = function(matrix, k) {
3.    let n = matrix.length;
4.    let upper = ~~Math.sqrt(k - 1);
5.    let result = [matrix[upper][upper]];
6.    for( let i = 0; i < upper; i++ )
7.    {
8.        for( let j = upper; j < n; j++ )
9.        {
10.            result.push(matrix[i][j]);
11.        }
12.    }
13.    for( let i = 0; i < upper; i++ )
14.    {
15.        for( let j = 0; j < n; j++ )
16.        {
17.            result.push(matrix[j][i]);
18.        }
19.    }
20.    return result.sort((a, b)=>a - b)[k - 1];
21.};

解法二

参考来源

因为行和列都是有序的，所以行 i 肯定有 i 个比他小的数，列 j 肯定比 j - 1大 
只需要二分找到当前下界和上界的中值，然后对于每个中值，用这个性质从左下角开始查找，找到比这个数小的数的个数 
用这个个数和k比较，逼近出结果

1.//Javascript
2./**
3. * @param {number[][]} matrix
4. * @param {number} k
5. * @return {number}
6. */
7.let kthSmallest = function (matrix, k) {
8.    let left = matrix[0][0];
9.    let right = matrix[matrix.length - 1][matrix.length - 1];
10.    while (left < right) 
11.    {
12.        let mid = (left + right) >> 1;
13.        let cnt = search_less_equal(matrix, mid);
14.        if (cnt < k) 
15.        {
16.            left = mid + 1;
17.        }
18.        else
19.        {
20.            right = mid;
21.        }
22.    }
23.    return left;
24.}
25.let search_less_equal = function (matrix, target) {
26.    let n = matrix.length;
27.    let i = n - 1;
28.    let j = 0;
29.    let res = 0;
30.    while (i >= 0 && j < n) 
31.    {
32.        if (matrix[i][j] <= target) 
33.        {
34.            res += i + 1;
35.            ++j;
36.        } 
37.        else 
38.        {
39.            --i;
40.        }
41.    }
42.    return res;
43.}

End