欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

九章算法 | Amazon 面试题:排序矩阵中的从小到大第k个数

程序员文章站 2022-07-14 17:36:04
...

在一个排序矩阵中找从小到大的第 k 个整数。

排序矩阵的定义为:每一行递增,每一列也递增。

在线评测地址:LintCode 领扣

样例 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我们就可以减小上界

否则就可以提高下界

2. 对于二分出来的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;
    }
}

更多题解参考:九章算法