378.Kth Smallest Element in a Sorted Matrix

只有我對這題目很感冒嗎, 什麼叫第k個最小的,

看了https://stackoverflow.com/questions/15179536/kth-smallest-element-in-sorted-matrix

才知道第k個最小的就是第k大的

第一個最小的, 就是最小的

好吧, 我資質駑鈍, 我們開始吧

看完discuss, 恩 這是鬼吧, 這到底誰想的到XD

他說明提到我們仍然可以把這個矩陣, 想成跟一個array一樣, 我們知道一開始的最大值跟最小值分別會在這個矩陣的左上(start)跟右下(end), 然後我們可以給出一個mid(start + end / 2), 通過看整個矩陣, 去計算有多少數字小於這個mid(count), 倘若 count < k, 代表我們給的mid太小, 更新start, 反之, 就更新end, 疑, 那start end, 要跟新到多少呢, 在計算count的同時, 紀錄最靠近mid的大小兩值, 並且將座標記下來, 就是用在這更新

可以多舉個例子看, 這需要花點時間理解

binary search真的高深莫測…..

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
int n = matrix.size();
    int start = matrix[0][0], end = matrix[n - 1][n - 1];
    while (start < end) {
      int mid = start + (end - start) / 2;
      // first number is the smallest and the second number is the largest
      pair<int, int> smallLargePair = {matrix[0][0], matrix[n - 1][n - 1]};
      int count = countLessEqual(matrix, mid, smallLargePair);
      if (count == k) {
        return smallLargePair.first;
      }
if (count < k) {
        start = smallLargePair.second;  // search higher
      } else {
        end = smallLargePair.first;  // search lower
      }
    }
return start;
  }
private:
  static int countLessEqual(vector<vector<int>> &matrix, int mid, pair<int, int> &smallLargePair) {
    int count = 0;
    int n = matrix.size(), row = n - 1, col = 0;
    while (row >= 0 && col < n) {
      if (matrix[row][col] > mid) {
        // as matrix[row][col] is bigger than the mid, let's keep track of the
        // smallest number greater than the mid
        smallLargePair.second = min(smallLargePair.second, matrix[row][col]);
        row--;
      } else {
        // as matrix[row][col] is less than or equal to the mid, let's keep track of the
        // biggest number less than or equal to the mid
        smallLargePair.first = max(smallLargePair.first, matrix[row][col]);
        count += row + 1;
        col++;
      }
    }
    return count;
  }
};

我自己寫的面目全非版

class Solution {
  public:
    int findKthCount(vector<vector<int>> &matrix, int target, int &smaller,
                     int &larger) {
        int count = 0;
        for (int i = 0; i < matrix.size(); i++) {
            for (int j = 0; j < matrix[0].size(); j++) {
                if (matrix[i][j] <= target) {
                    count++;
                    smaller = max(smaller, matrix[i][j]);
                } else {
                    larger = min(larger, matrix[i][j]);
                }
                if (j == 0 && matrix[i][j] > target) {
                    break;
                }
            }
        }
        return count;
    }
int kthSmallest(vector<vector<int>> &matrix, int k) {
        int m = matrix.size();
        int n = matrix[0].size();
        int start = matrix[0][0];
        int end = matrix[m - 1][n - 1];
        while (start < end) {
            int mid = (start + end) / 2;
            int smaller = INT_MIN;
            int larger = INT_MAX;
            int cnt = findKthCount(matrix, mid, smaller, larger);
            if (cnt == k) {
                return smaller;
            }
            if (cnt < k) {
                start = larger;
            } else {
                end = smaller;
            }
        }
        return start;
    }
};

最後為什麼start 不是 ≤ end, 可以用一個例子很快就能判斷了

[1,5], target = 2

就換發現start跟end一樣, 如果是小於等於會沒辦法出循環

class Solution {
public:
    int countNonBigger(vector<vector<int>>& matrix, int target){
        int m = matrix.size();
      
        int res = 0;
        for(int i = 0; i < m; i++){
            int j = m - 1;
            while(j>=0&&matrix[i][j]>target)
                j--;
            res+=j+1;
        
        }
        return res;
    }
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int n = matrix.size();
        int l = matrix[0][0];
        int r = matrix[n - 1][n-1];
        while(l < r){
            int mid = (l + r) /2;
            int count = countNonBigger(matrix, mid);
            if(count < k){
                l = mid + 1;
            }else{
                r = mid ;
            }
        }
        return l;
    }
};