C ++乘法表中的Kth最小数

假设我们知道一个乘法表。但是我们可以从乘法表中快速找出第k个最小的数字吗？因此，如果我们必须乘以高度m和am * n乘法表的长度n以及一个正整数k，则需要在此表中找到第k个最小的数字。

因此，如果m = 3且n = 3且k为6，则输出将为4，这是因为乘法表类似于-

第六个最小元素是4，例如[1,2,2,3,3,4,6,6,9]

为了解决这个问题，我们将遵循以下步骤-

• 定义一个函数ok()，它将花费m，n，x，

• ret：= 0

• 对于初始化i：= 1，当i <= n时，更新（将i增加1），-

• temp：= x / i和m的最小值

• ret：= ret +温度

• 返回ret

• 从主要方法中，执行以下操作-

• ret：= -1，低：= 1，高：= m * n

• 当低<=高时，执行-

• 低：=中+ 1

• 高：=中-1

• ret：=中

• 中：=低+（高-低）/ 2

• cnt：= ok(m,n,mid)

• 如果cnt> = k，则-

• 除此以外

• 返回ret

让我们看下面的实现以更好地理解-

示例

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int ok(int m, int n, int x){
      int ret = 0;
      for(int i = 1; i <= n; i++){
         int temp = min(x / i, m);
         ret += temp;
      }
      return ret;
   }
   int findKthNumber(int m, int n, int k) {
      int ret = -1;
      int low = 1;
      int high = m * n ;
      while(low <= high){
         int mid = low + (high - low)/ 2;
         int cnt = ok(m, n, mid);
         if(cnt >= k){
            high = mid - 1;
            ret = mid;
         }else low = mid + 1;
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.findKthNumber(3,3,6));
}

输入值

“2*”

输出结果

4