LeetCode-378.有序矩阵中第k小的元素、二分查找_leetcode378

给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。示例：matrix = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ], k = 8, 返回 13。
力扣（LeetCode）第378题

值域范围

  由于矩阵内元素是从左上到右下递增的，则矩阵中元素的最小值 left 为 matrix[0][0] ,最大值 right 为 matrix[matrix.size()-1][matrix[0].size()-1]，矩阵中所有元素的值均在范围 [ left , right ] 内。

元素个数单调性

  在范围 [ left , right ] 中任取一个值 mid，那么矩阵中不大于 mid 的元素肯定都分布在矩阵的左上角，如下图所示：

  图中不大于 mid 的元素和大于 mid 的元素用一条折线把矩阵分为了左右两部分。
  不大于 mid 的元素个数 count 沿着折线走一遍即可用线性的时间复杂度得到，并且 mid 越大时，count 越大，满足单调递增。

二分查找

  根据以上分析，对于求不大于 mid 的元素个数 count ，满足二分查找的性质。
  对矩阵中的元素按值域进行二分，每次二分都把矩阵划分成了[left , mid] 与[mid + 1, right]两部分。当 count < k 时, 说明mid太小了, 我们应该在[mid + 1, right] 这个范围里查找，否则在[left, mid]范围里查找。

正确性证明

  当 left 和 right 相等时，返回 left 的值，怎么证明 left 一定在矩阵中呢？
  首先矩阵中一定存在第 k 小的数，假设第 k 小数为 m ，并且 m 的个数为 x 个；当前取值 mid 时，不小于 mid 的元素个数为 count ,分三种情况：
  ①．mid = m -1：
  此时 count 一定小于 k ,则设置 left = mid +1，此时 left = m，right >= mid+1；继续二分，最终 right 也会收敛到等于 mid+1；left = right 时返回，返回值为 m，满足要求；
  ②．mid = m +1：
  此时 count 一定大于 k ,则设置 right = mid ，此时 right = m+1，left < mid ；继续二分，最终 left 放大到 mid-1, right 也会收敛到 mid-1，left = right 时返回，返回值为 m，满足要求；
  ③．mid = m ：
  此时 count 不小于 k ,则设置 right = mid，此时 right = m ，left < mid；继续二分，当 left 放大到 mid -1 时 count 依然小于k ,需要设置 left +1 ,left = right 时返回，返回值为 m，满足要求；
  因为 mid = (left + right) / 2，当 left < right 时, mid 永远取不到right，即我们最终得到是一个左边界值。假设存在一个不在矩阵中的数 x 满足条件，因为需要满足矩阵中的前 k 个元素都小于 x ，则 x 一定大于 left 。
  综上，最终二分查找得到的值一定在矩阵内。

代码示例

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int left = matrix[0][0];
        int right = matrix[matrix.size()-1][matrix[0].size()-1];
        while( left < right )
        {
            int mid = left + (right - left) /2;
            int midcount = getCountOfvalue(matrix,mid);
            if( midcount < k )
            {
                left = mid+1;
            } 
            else
            {
                right = mid;
            }
        }
        return left;
    }
    int getCountOfvalue(vector<vector<int>>& matrix,int num)
{
        int count = 0;
        int i = matrix.size()-1;
        int j = 0;
        while( i > -1 && j < matrix[0].size())
        {
            if( matrix[i][j] <= num )
            {
                count += i +1;//一列一列的相加
                j++;
            }
            else
            {
                i--;
            }
        }
        return count;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40