Straight Forward O(min(klog(k), n^2)) solution using nth_element of C++


  • 0
    L

    The solution is straight forward. Put all 'possible' elements to another vector and use nth_element to that vector, which is linear time.

    'possible' elements are those whose index i, j satisfies
    i < k && i < matrix.size()
    j < matrix.size() && (i + 1) * (j + 1) <= k

    Note that for any k, for each i, there are at most [k / (i + 1)] 'possible' elements with on ith row. So there will be approximately klog(k) 'possible' elements totally. Also, number of 'possible' elements can be no more than n^2.

    class Solution {
    public:
        int kthSmallest(vector<vector<int>>& matrix, int k) {
            vector<int> m;
            for(int i = 0; i < k && i < matrix.size(); ++i)
                for(int j = 0; j < matrix.size() && (i + 1) * (j + 1) <= k; ++j)
                    m.push_back(matrix[i][j]);
    
            nth_element(m.begin(), m.begin() + k - 1, m.end());
            return *(m.begin() + k - 1);
        }
    };
    

  • 0
    S

    seems "j < matrix.size()" is a typo of "j < matrix[0].size()"


  • 0
    S
    This post is deleted!

  • 0
    S

    @st.wanng No. The matrix is n*n, so it's not a typo.


  • 0

    nth_element isn't O(n) but only average O(n).


  • 0
    L

    @StefanPochmann

    There is worst case O(n) algorithm for doing nth_element anyway......


Log in to reply
 

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