二维表的第k大的数

链接：https://www.nowcoder.com/questionTerminal/98929bfe8f6b4beba5838285ae99aa6f
来源：牛客网

在一块长为n，宽为m的场地上，有n✖️m个1✖️1的单元格。每个单元格上的数字就是按照从1到n和1到m中的数的乘积。具体如下

n = 3, m = 3

1 2 3

2 4 6

3 6 9

给出一个查询的值k，求出按照这个方式列举的的数中第k大的值v。

例如上面的例子里，

从大到小为(9, 6, 6, 4, 3, 3, 2, 2, 1)

k = 1, v = 9

k = 2, v = 6

k = 3, v = 6

…

k = 8, v = 2

k = 9, v = 1

输入描述:

只有一行是3个数n, m, k 表示场地的宽高和需要查询的k。使用空格隔开。

输出描述:

给出第k大的数的值。

示例1

输入

3 3 4

输出

4

备注:

【数据范围】
100%的数据
1 <= n, m <= 40000
1 <= k <= n * m
30%的数据
1 <= n, m <= 1000

二维表的第k大数

import java.util.*;
public class Main {
    public static void problem5_2020() {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int k = scanner.nextInt();
        int left = 1;
        int right = m * n;
        k = m * n - k + 1;
        while (left < right) {
            // 注意int类型溢出问题！
            int mid = (int)(((long)left + right) / 2);
            // 求小于等于 mid 的数量
            int row = mid / m;
            int count = row * m;
            for (int i = row + 1; i <= n; i++) {
                count += mid / i;
            }
            if (count < k) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        System.out.println(left);
    }

    public static void main(String[] args) {
        problem5_2020();
    }
}

二分查找

import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int M = in.nextInt();
        int K = in.nextInt();
        
        int l = 0;
        int h = M * N;
        //反向序号
        K = M * N - K + 1;
        while (l <= h) {
            int mid = l + (h - l) / 2;
            // 假定以mid作为最大数的所在行curRow; 由矩阵的特点可知：
            // curRow的上一行所有的数都将小于mid，缩小查找范围
            int curRow = mid / M;
            // 同理，获取所在列curCol；
            int curCol = mid / N;
            int cnt = curRow * M + curCol * (N - curRow);
            // 剩下右下角一个小矩形
            for (int i = curRow + 1; i <= N; i++) {
                for (int j = curCol + 1; j <= M && (i * j <= mid); j++) {
                    cnt++;
                }
            }
            // 如果当前的数量多于k那么在前边，否则在后边
            if (cnt >= K) {
                h = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        System.out.println(l);
    }
}

赏

谢谢你请我吃糖果

微信