K-th Nhỏ nhất trong Thứ tự từ vựng trong C ++

Giả sử chúng ta có hai giá trị n và k. Chúng ta phải tìm số nguyên nhỏ nhất từ ​​điển thứ k trong phạm vi từ 1 đến n. Vì vậy, nếu đầu vào là n =14 và k =3, thì đầu ra sẽ là 11, vì dãy sẽ là [1, 10, 11, 12, 13, 14, 2, 3, 4, 5, 6, 7 , 8, 9], thì số thứ k là 11.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một hàm findKthNumber (), hàm này sẽ nhận n, k,
• curr:=1
• (giảm k đi 1)
• while k khác 0, do -
  • step:=gọi hàm calcSteps (n, curr, curr + 1)
  • nếu các bước <=k, thì -
    • k:=k - các bước
    • (tăng độ cong lên 1)
  • Mặt khác
    • curr:=curr * 10
    • k:=k - 1
  • return curr
• Xác định một hàm calcSteps (), hàm này sẽ lấy nax, n1, n2,
• ret:=0
• while n1 <=nax, do -
  • ret:=ret + tối thiểu nax + 1 và n2 - n1
  • n1:=n1 * 10
  • n2:=n2 * 10
• trả lời lại

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

14,3

Đầu ra

11