C# solution: do merge first.


  • 0
    N
    public class Solution {
        public int KthSmallest(int[,] matrix, int k) {
            var n = matrix.GetLength(0);
            var row = (k-1)/n;
            var col = (k-1)%n;
            
            var m = new int[n*n];
            for(var i=0;i<n;i++){
                m[i] = matrix[0,i];
            }
            for(var i=1;i<n;i++){
                merge(m, matrix, i);
            }
            
            return m[k-1];
        }
        
        public void merge(int[] m, int[,] matrix, int row) {
            var older = matrix.GetLength(0) * row -1;
            var newIndex = matrix.GetLength(0) * (row+1) -1;
            
            var j = matrix.GetLength(0)-1; // index of matrix, cols
            while(older>=0 && j>=0){
                if(m[older]>=matrix[row, j]){
                    m[newIndex--] = m[older--];
                }
                else{
                    m[newIndex--] = matrix[row, j--];
                }
            }
            
            while(older>=0){
                m[newIndex--] = m[older--];
            }
            
            while(j>=0){
                m[newIndex--] = matrix[row,j--];
            }
        }
    }
    

Log in to reply
 

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