378. Kth Smallest Element in a Sorted Matrix

發表於 | 分類於

problem

solution

option 1 - STL to store

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix , int k) {
        vector<int> vec;
        int n = matrix.size(), m = matrix[0].size();
        for(int i=0 ;i<n;++i){
            for(int j = 0;j<m;++j) vec.push_back(matrix[i][j]);
        }
        sort(vec.begin(), vec.end());
        return vec[k-1];
    }
};

option 2 - heap

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix , int k) {
        priority_queue<int, vector<int>, greater<int>> pq;
        int n = matrix.size(), m = matrix[0].size();
        for(int i=0 ;i<n;++i){
            for(int j = 0;j<m;++j) pq.push(matrix[i][j]);
        }
        k--;
        while(k--) pq.pop();
        return pq.top();
    }
};
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
class Solution {
public:
    int lower_bound(vector<int> & nums, int target){
        //left lower
        int l = 0, r = nums.size();
        while(l<r){
            int mid = l + (r-l)/2;
            if(nums[mid] <= target ) l = mid+1;
            else r = mid;
        }
        return l ;
    }
    int kthSmallest(vector<vector<int>>& matrix , int k) {
        
        int n = matrix.size(), m = matrix[0].size();
        int left = matrix[0][0], right = matrix[n-1][m-1];
        while(left<right){
            int mid = left + (right-left)/2;
            int cnt = 0;
            // cnt 計算陣列有多少數字小於等於mid
            for(int i=0;i<n;++i){
                cnt+=lower_bound(matrix[i], mid);
            }
            if(cnt > k) right = mid;
            else if(cnt<k) left = mid + 1;
            else right = mid;
            
        }
        return left;
    }
};

analysis

  • option 1
    • time complexity O(n^2)
    • space O(n)
  • option 2
    • time complexity O(n^2)
    • space complexity O(n)