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