Skip to content

668. Kth Smallest Number in Multiplication Table

668. Kth Smallest Number in Multiplication Table

题目: https://leetcode.com/problems/kth-smallest-number-in-multiplication-table/

难度: Hard

题意：

  1. 给定一个m和n，表示生成m*n的矩阵，矩阵里面的值为a(i,j) = i * j
  2. 求这个矩阵所有数中第k小是哪个数

思路：

  • 由于m，n，k都很大，因此不能用排序或者堆排序的方式进行解答
  • 我们可以二分结果，因为结果肯定是在0到n*m之间的某个数
  • 假设二分值是p，我们需要判断整个矩阵中小于p有多少个，只需要遍历一遍，根据p/i来判断第i行小于p有多少个，累加

解法：

#include<cstdio>
#include<cstring>

class Solution {
public:
    int a[1001][1001];
    int MOD = 1000000007;
    int kInversePairs(int n, int k) {
        memset(a, 0, sizeof(a));
        a[0][0] = 1;
        for (int i = 1;i <= n;i++) {
            int s = 0;
            for (int j = 0;j <= k;j++) {
                s += a[i - 1][j];
                if (s >= MOD) {
                    s -= MOD;
                }
                if (j - i >= 0) {
                    s -= a[i - 1][j - i];
                    if (s < 0) {
                        s += MOD;
                    }
                }
                a[i][j] = s;
            }
        }
        return a[n][k];
    }
};
回到顶部