สมมติว่าเรามีสองค่า n และ k เราต้องหาจำนวนเต็มที่น้อยที่สุดที่ kth เกี่ยวกับคำศัพท์ในช่วง 1 ถึง n ดังนั้นหากอินพุตเป็น n =14 และ k =3 เอาต์พุตจะเป็น 11 เนื่องจากลำดับจะเป็น [1, 10, 11, 12, 13, 14, 2, 3, 4, 5, 6, 7 , 8, 9] แล้วเลข k คือ 11
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- กำหนดฟังก์ชัน findKthNumber() ซึ่งจะใช้เวลา n, k,
- สกุลเงิน :=1
- (ลดลง k โดย 1)
- ในขณะที่ k ไม่ใช่ศูนย์ ให้ทำ −
- ขั้นตอน :=เรียกใช้ฟังก์ชัน calcSteps(n, curr, curr + 1)
- ถ้าขั้นตอน <=k แล้ว −
- k :=k - ขั้นตอน
- (เพิ่มสกุลเงินขึ้น 1)
- มิฉะนั้น
- 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
ผลลัพธ์
11
