Java solution


  • 0
    C

    sorry my code is really messy
    what i did is to remove all cells that cant contain the kth smallest number and just sort the rest of the numbers

    public class Solution {
    public static void quickSort(int[] arr, int low, int high) {
    if (arr == null || arr.length == 0)
    return;

    	if (low >= high)
    		return;
    
    	int middle = low + (high - low) / 2;
    	int pivot = arr[middle];
    
    	int i = low, j = high;
    	while (i <= j) {
    		while (arr[i] < pivot) {
    			i++;
    		}
    
    		while (arr[j] > pivot) {
    			j--;
    		}
    
    		if (i <= j) {
    			int temp = arr[i];
    			arr[i] = arr[j];
    			arr[j] = temp;
    			i++;
    			j--;
    		}
    	}
    
    	if (low < j)
    		quickSort(arr, low, j);
    
    	if (high > i)
    		quickSort(arr, i, high);
    }
    
    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        if (k == 1) {return matrix[0][0];}
        if (k == n*n) {return matrix[n-1][n-1];}
        
        int min_line = -1;
        int max_line = -1;
        for (int i = 1; i < 2*n; i++) {
            if ((i > k)&&(i <= n)&&(min_line == -1)) min_line = i;
            else if (((i-n+1)*n > k)&&(i > n)&&(min_line == -1)) min_line = i;
            if (((i-1)*n+1 >= k)&&(i <= n)&&(max_line == -1)) max_line = i;
            else if ((((n-1)*n+(i-n+1)) >= k)&&(i > n)&&(max_line == -1)) max_line = i;
        }
        
        int new_k = -1;
        if (max_line-1 > n) {
            new_k = n*(1+n)/2;
            for (int i = n+1; i < max_line; i++) {
                new_k += (i-2*(i-n));
            }
            new_k = k-new_k;
        } else {
            new_k = k-(max_line-1)*(1+max_line-1)/2;
        }
        
        int counter = 0;
        for (int i = max_line; i < min_line; i++){
            int temp = 0;
            if (i <= n) {
                temp = i;
                counter += temp;
            } else {
                temp = i-2*(i-n);
                counter += temp;
            }
        }
        
        int[] A = new int[counter];
        int p = 0;
        for (int i = max_line; i < min_line; i++) {
            int start_i = i;
            if (i > n) start_i -= (i-n);
            int start_j = 1;
            if (i > n) start_j = (i-n+1);
            
            int temp = 0;
            if (i <= n) {
                temp = i;
            } else {
                temp = i-2*(i-n);
            }
            
            for (int j = p; j < temp+p; j++) {
                A[j] = matrix[start_i-1][start_j-1];
                start_i--;
                start_j++;
            }
            p+=temp;
        }
        quickSort(A,0,A.length-1);
        return A[new_k-1];
    }
    

    }


Log in to reply
 

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