C++の掛け算の九九でK番目に小さい数

1つの掛け算の九九について知っていると仮定します。しかし、九九からk番目に小さい数をすばやく見つけることができますか？したがって、高さm、長さnのa m * n掛け算の九九、および1つの正の整数kが必要な場合、この表でk番目に小さい数を見つける必要があります。

したがって、m=3およびn=3でkが6の場合、出力は4になります。これは、掛け算の九九が-

6番目に小さい要素は[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 + temp
• return ret
• メインの方法から、次の手順を実行します-
• ret：=-1、low：=1、high：=m * n
• 低い<=高い間、-
  を実行します
  • 中：=低+（高-低）/ 2
  • cnt：=ok（m、n、mid）
  • cnt> =kの場合、-
    • 高：=中-1
    • ret：=mid
  • それ以外の場合
    • 低：=中+1
• return 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