面試真題詳解：排序矩陣中的從小到大第k個數

在一個排序矩陣中找從小到大的第 k 個整數。

排序矩陣的定義為：每一行遞增，每一列也遞增。

線上評測位址：

領扣題庫官網 樣例 1:

輸入:
[
  [1 ,5 ,7],
  [3 ,7 ,8],
  [4 ,8 ,9],
]
k = 4
輸出: 5           

樣例 2:

輸入: 
[
  [1, 2],
  [3, 4]
]
k = 3
輸出: 3           

算法：二分

題目中矩陣n行m列，每行每列都是單調的，我們可以按照行或者列做

把n行當成n個數組

即求n個有序數組裡第k小值是多少

如果序列有序，則可以用一種更有效率的查找方法來查找序列中的記錄，這就是折半查找法，又稱為二分搜尋。

折半查找的基本思想：減少一半的查找序列的長度，分而治之地進行關鍵字的查找。他的查找過程是：先确定待查找記錄的所在的範圍，然後逐漸縮小查找的範圍，直至找到該記錄為止（也可能查找失敗）。

在最簡單的形式中，二分查找對具有指定左索引和右索引的連續序列進行操作。這就是所謂的查找空間。二分查找維護查找空間的左、右和中間訓示符，并比較查找目标或将查找條件應用于集合的中間值；如果條件不滿足或值不相等，則清除目标不可能存在的那一半，并在剩下的一半上繼續查找，直到成功為止。如果查以空的一半結束，則無法滿足條件，并且無法找到目标。

本題思路

1. 二分第k小的是多少

   二分解決判定性問題

我們二分出來第k小是x， 統計出有num個元素小于等于x

如果num≥k我們就可以減小上界

否則就可以提高下界

1. 對于二分出來的x，判斷有多少個元素是小于等于x的

   我們可以先找元素大于x的，然後再用元素總個數減去大于x的元素個數

如何求有多少大于x的元素，我們可以再用一次二分查找upperbound函數，對n個數組都執行一次upperbound查找每個數組有多少比x大的

import java.util.Comparator;import java.util.PriorityQueue;
public class Solution {

    public long calc(int x, int[][] matrix) {
        long num = 0;
        for(int i = 0; i < matrix.length; i++) {
            int left = -1, right = matrix[i].length, pos = -1;
            //二分upper_bound查找多少個比x大的
            while(left + 1 < right) {
                int mid = left + (right - left) / 2;
                if(matrix[i][mid] > x) {
                    right = mid;
                    pos = mid;
                } else {
                    left = mid;
                }
            }
            if(pos == -1) {
                num += 0;
            } else {
                num += matrix[i].length - pos;
            }
        }
        return num;
    }
    /**
     * @param matrix: a matrix of integers
     * @param k: An integer
     * @return: the kth smallest number in the matrix
     */
    public int kthSmallest(int[][] matrix, int k) {
        // write your code here
        int left = matrix[0][0], right = matrix[0][0];

        //矩陣行數
        long n = matrix.length;
        //矩陣列數
        long m = matrix[0].length;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                //确定二分上下界
                left = Math.min(left, matrix[i][j]);
                right = Math.max(right, matrix[i][j]);
            }
        }
        left -= 1;
        right += 1;
        while(left + 1 < right) {
            //判定mid是不是第k小
            int mid = left + (right - left) / 2;
            long num = calc(mid, matrix);
            //如果比mid小的超過k個，就可以縮小上界，否則提高下界
            if(n * m - num >= (long)k) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return right;
    }
}           

更多題解參考：

九章官網solution