Same solution with 378. Kth Smallest Element in a Sorted Matrix but difficulties are different?


  • 0
    O

    This problem and 378. Kth Smallest Element have same solution. Although former is given as hard, latter is given as medium.

    What is the reason of this difference?

    My solution for this problem

    class Solution {
    private:
    	int countSmaller(int m, int n, int target){
    		int count = 0;
    		for(int i=1;i<=n;i++){
    			if(m*i > target){
    				m--;
    				i--;
    			}
    			else
    				count += m;
    		}
    		return count;
    	}
    
    public:
        int findKthNumber(int m, int n, int k) {
            int low = 1, high = m*n;
            while(low <= high){
            	int mid = (low + high) / 2;
            	int count = countSmaller(m, n, mid);
            	if(count < k)
            		low = mid + 1;
            	else
            		high = mid - 1;
            }
            return low;
        }
    };
    

    and, my solution for 378. Kth Smallest Element in a Sorted Matrix

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

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.