C++의 사전순에서 K번째로 가장 작은 것

<시간/>

두 개의 값 n과 k가 있다고 가정합니다. 1에서 n 사이의 범위에서 사전식으로 k번째로 작은 정수를 찾아야 합니다. 따라서 입력이 n =14 및 k =3인 경우 시퀀스는 [1, 10, 11, 12, 13, 14, 2, 3, 4, 5, 6, 7이므로 출력은 11이 됩니다. , 8, 9], k번째 숫자는 11입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

findKthNumber() 함수를 정의합니다. n, k,
커:=1
(k를 1씩 감소)
k가 0이 아닌 동안 −
- steps :=calcSteps(n, curr, curr + 1) 함수 호출
- 단계가 <=k이면 -
  - k :=k - 단계
  - (통화를 1씩 증가)
- 그렇지 않으면
  - curr :=curr * 10
  - k :=k - 1
- 반환 통화
calcSteps() 함수를 정의하면 nax, n1, n2,
ret :=0
n1 <=nax인 동안 −
- ret :=ret + nax + 1 및 n2 – n1의 최소값
- n1 :=n1 * 10
- n2 :=n2 * 10
반환

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

예시

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
   int findKthNumber(int n, int k) {
      int curr = 1;
      k--;
      while(k){
         int steps = calcSteps(n, curr, curr + 1);
         if(steps <= k){
            k -= steps;
            curr++;
         }else{
            curr *= 10;
            k -= 1;
         }
      }
      return curr;
   }
   int calcSteps(lli nax, lli n1, lli n2){
      int ret = 0;
      while(n1 <= nax){
         ret += min(nax + 1, n2) - n1;
         n1 *= 10;
         n2 *= 10;
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.findKthNumber(14,3));
}

입력

14,3