C++의 곱셈표에서 K번째로 작은 수

하나의 구구단에 대해 알고 있다고 가정합니다. 그런데 곱셈표에서 k번째로 작은 수를 빨리 찾을 수 있을까요? 따라서 m * n 곱셈표의 높이 m과 길이 n, 그리고 하나의 양의 정수 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
• 반환
• 메인 방법에서 다음을 수행하십시오. -
• ret :=-1, 낮음 :=1, 높음 :=m * n
• 낮은 <=높은 동안 −
  • 중간 :=낮음 + (높음 - 낮음) / 2
  • cnt :=ok(m, n, mid)
  • cnt>=k이면 -
    • 높음 :=중간 - 1
    • ret :=중간
  • 그렇지 않으면
    • 낮음 :=중간 + 1
• 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예

#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