当前位置:   article > 正文

leetcode378+Kth Smallest Element in a Sorted Matrix+二分左小角判断开始

leetcode378+Kth Smallest Element in a Sorted Matrix+二分左小角判断开始

链接

  1. //从左下角进行遍历,和之前那个找是否存在某个元素(右上角开始搜索)相反
  2. class Solution {
  3. public:
  4. int kthSmallest(vector<vector<int>>& matrix, int k) {
  5. int left=matrix[0][0],right=matrix.back().back();
  6. while(left<right){
  7. //int mid=(left+right)/2;
  8. int mid= left+ (right-left)/2;
  9. int index=search(matrix,mid);
  10. if(index<k)
  11. left=mid+1;
  12. else
  13. right=mid;
  14. }
  15. return left;
  16. }
  17. int search(vector<vector<int>>& matrix, int mid){
  18. int i=matrix.size()-1, j=0,cnt=0; //从左下角开始
  19. while(i>=0&&j<matrix[0].size()){
  20. if(matrix[i][j]<=mid){ //也是先从列开始
  21. j+=1;
  22. cnt += i+1; //那个元素所在的整列元素都小于 target。i的index从0开始的,所以要+1
  23. }else{ //再从行开始
  24. i-=1;
  25. }
  26. }
  27. return cnt;
  28. }
  29. };

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/982749
推荐阅读
相关标签
  

闽ICP备14008679号