New Solution!!! NOT USE Binary Search or Heap


  • 0

    Inspired by Super Ugly Number, 90ms, O(N^3), Let me know if you can improve, thx :)

    public class Solution {
        public int kthSmallest(int[][] matrix, int k) {
            int n = matrix.length;
            //idx of each row
            int[] idx = new int[n];
            int result =0;
            while(k>0){
                int min = Integer.MAX_VALUE;
                for(int j=0;j<n;j++){
                    if(idx[j] == n){
                        continue;
                    }
                    min = Math.min(min, matrix[j][idx[j]]);
                }
                for(int j=0;j<n;j++){
                    if(idx[j]==n){
                        continue;
                    }
                    if(min == matrix[j][idx[j]] && idx[j]<n){
                          idx[j]++;
                          k--;
                    }
                    if(k<=0){
                       return min;
                    }
                }
                result=min;
            }
            return result;
        }
    }

  • 0

    That's clearly not O(n^2) but only O(n^3). Just think of a matrix without duplicates and k=n^2.


  • 0

    @StefanPochmann you are right, I have correct the time complexity :)


Log in to reply
 

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