Java Quick Selection (convert 2D to 1D)


  • 0

    Think about the Quick Selection approach to find the Kth smallest element in an 1d array. Can we possibly use the same strategy in an 2d array?

    If we can, in some way, convert 2d matrix to a 1d array, then we can use Quick Selection the same way.

    Matrix width is int n = matrix[0].length and we can convert every index (i, j) in 2d array to and 1d format, and vice versa.

    • int index = i * n + j

    • i = index / n

    • j = index % n

    And now, we can use this trick to treat 2d matrix as and 1d array, and apply Quick Selection easily.

    public class Solution {
    	int m;
    	int n;
        public int kthSmallest(int[][] matrix, int k) {
    //if m and n are very very large, then we only consider the top left matrix with width of k, since Kth element will never sit out side square k.
            m = Math.min(matrix.length, k);
            n = Math.min(matrix[0].length, k);
    //quick selection range : start = 0, end = m*n-1;
            int kth = quickselect(matrix, 0, m * n - 1, k);
            return get(matrix, kth);
        }
        
    /**
    *This function is a general quick selection, by using helper function of get and set, you can treat the indexes as are in a 1D array. 
    */
        private int quickselect(int[][] matrix, int start, int end, int k) {
        	int pivot = get(matrix, end);
        	int left = start -1;
        	int right = end;
        	while (true) {
        		while(get(matrix, ++left) < pivot);
        		while(right > 0 && get(matrix, --right) > pivot);
        		if (left >= right) break;
        		else {
        			swap(matrix, left, right);
        		}
        	}
        	swap(matrix, left, end);
        	int num = left - start + 1;
        	if (k == num) return left;
        	else if (num > k) return quickselect(matrix, start, left - 1, k);
        	else return quickselect(matrix, left + 1, end, k - num);
        }
        
        private int get(int[][] matrix, int index) {
        	return matrix[index / n][index % n];
        }
        
        private void swap(int[][] matrix, int m1, int m2) {
        	int tmp = matrix[m1/n][m1%n];
        	matrix[m1/n][m1%n] = matrix[m2/n][m2%n];
        	matrix[m2/n][m2%n] = tmp;
        }
    }
    

  • 0
    B

    But that's a O(n^2) solution... (n=length of row, n^2 = number of cells)


Log in to reply
 

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