leetcode378. Kth Smallest Element in a Sorted Matr

dailybird 發(fā)布于2019-08-16 15:05 / 2551人閱讀

摘要：因此我們可以采用部分元素堆排序即可。即我們每次只需要可能構(gòu)成第個元素的值進(jìn)行堆排序就可以了。

題目要求

Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

Example:

matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,

return 13.
Note: 
You may assume k is always valid, 1 ≤ k ≤ n2.

在一個從左到右，從上到下均有序的二維數(shù)組中，找到從小到第k個數(shù)字，這里需要注意，不要求一定要是唯一的值，即假設(shè)存在這樣一個序列1,2,2,3，則第三個數(shù)字是2而不是3。

思路一：優(yōu)先隊列

當(dāng)涉及到從一個集合中查找一個元素這樣的問題時，我們往往會立刻想到查找的幾種方式：有序數(shù)組查找，無序數(shù)組查找，堆排序。這里如果將二維數(shù)組轉(zhuǎn)化為一維有序數(shù)組，成本未免太大了。同理，將其中所有元素都轉(zhuǎn)化為堆，也會存在內(nèi)存不足的問題。因此我們可以采用部分元素堆排序即可。即我們每次只需要可能構(gòu)成第k個元素的值進(jìn)行堆排序就可以了。

    public int kthSmallest(int[][] matrix, int k) {
        //優(yōu)先隊列
        PriorityQueue queue = new PriorityQueue();
        //將每一行的第一個元素放入優(yōu)先隊列中
        for(int i = 0 ; i{
        int x;
        int y;
        int value;
        
        public Tuple(int x, int y, int value) {
            this.x = x;
            this.y = y;
            this.value = value;
        }
        @Override
        public int compareTo(Tuple o) {
            // TODO Auto-generated method stub
            return this.value - o.value;
        }
    }

思路二：二分法查找

二分查找的核心問題在于，如何找到查找的上界和下屆。這邊我們可以矩陣中的最大值和最小值作為上界和下界。然后不停的與中間值進(jìn)行比較，判斷當(dāng)前矩陣中小于該中間值的元素有幾個，如果數(shù)量不足k，就將左指針右移，否則，就將右指針左移。直到左右指針相遇。這里需要注意，不能在數(shù)量等于k的時候就返回mid值，因為mid值不一定在矩陣中存在。

    public int kthSmallest2(int[][] matrix, int k){
        int low = matrix[0][0], high = matrix[matrix.length-1][matrix[0].length-1];
        while(low <= high) {
            int mid = low + (high - low) / 2;
            int count = 0;
            int i = matrix.length-1 , j = 0;
            //自矩陣左下角開始計算比mid小的數(shù)字的個數(shù)
            while(i>=0 && j < matrix.length){
                if(matrix[i][j]>mid) i--;
                else{
                    count+=i+1;
                    j++;
                }
            }
            if(count < k) {
                low = mid + 1;
            }else{
                high = mid - 1;
            }
        }
        return low;
    }