力扣寻找数组中第k小元素遇到的问题

Question

思路是用二分法筛选该元素位序，计算有多少元素小于等于该位序的元素，与期望值k比较，请问问题在哪，怎么改进

Answer 1

本题的二分法确实具有迷惑性，题主的二分法将矩阵的下标和矩阵的值搞混了。下图是题解中的矩阵举例，每行呈递增趋势，每列呈递增趋势，并不是后一行一定大于前一行，如matrix[3][0] < matrix[0][3]. 这可能是造成题主理解错题目的根本原因。

下面给出了修改后的代码，并附带了每一处修改的原因。代码经过leetcode验证通过率100%。

class Solution {
public:
    int kthSmallest(vector<vector<int>>&matrix,int k){
        int count=0;
        int n = matrix.size()*matrix[0].size();
        // int left=0;
        // int right=n-1; 修改此处【1】，left是矩阵的最小值，right是矩阵的最大值。
        int left = matrix[0][0];
        int right = matrix[matrix.size()-1][matrix.size()-1];
        int mid;
        while(left<right){
            mid=left+(right-left)/2;
            int i=matrix.size()-1,j=0;
            // count = 0; count每统计完一次要清零
            // while(i>=0&&j<=matrix[0].size()-1){
            //     if(matrix[i][j]>matrix[mid/n][mid%n]){ 修改此处【2】, 和【1】的修改理由相同，mid是数值不是下标
            //         j++;
            //     }
            //     else i--;
            //     count++;        // count的统计方式不对
            // }
            while(i>=0&&j<=matrix[0].size()-1){
                if(matrix[i][j]<=mid){
                    count += i+1; 
                    j++;
                }
                else i--;
            }
    
            // if(count>k){ 修改【3】，此处的二分法区间对应错误
            //     left=mid+1;
            // }
            // else if(count<k){
            //     right=mid-1;
            // }
            if(count >= k){
                right=mid;
            }
            else if(count<k){
                left = mid+1;
            }
        }
        // return matrix[mid/n][mid%n]; 这里同样是，left是返回值
        return left;
    }
};

关于第2处修改，题主可能会有疑惑，为什么count += i+1; 这里其实是按列统计的，如下图，扫描到6时，将6之上的一整列统计进去，因为其上的数必然小于6，也就小于mid。

关于返回值题主可能会疑惑怎么保证返回的left一定是矩阵中的值，leetcode的评论中有一句很精辟的理解

因为每次循环中都保证了第k小的数在left~right之间，当left==right时，第k小的数即被找出，等于right或left