資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中字典序第 K 小的數
假設我們有兩個值 n 和 k。我們需要找到 1 到 n 範圍內字典序第 k 小的整數。例如，如果輸入為 n = 14 和 k = 3，則輸出為 11，因為序列將為 [1, 10, 11, 12, 13, 14, 2, 3, 4, 5, 6, 7, 8, 9]，然後第 k 個數字為 11。
為了解決這個問題，我們將遵循以下步驟：
- 定義一個函式 findKthNumber()，它將接收 n、k 作為引數。
- curr := 1
- (將 k 減 1)
- 當 k 不為零時，執行以下操作：
- steps := 呼叫函式 calcSteps(n, curr, curr + 1)
- 如果 steps <= k，則：
- k := k - steps
- (將 curr 加 1)
- 否則
- curr := curr * 10
- k := k - 1
- 返回 curr
- 定義一個函式 calcSteps()，它將接收 nax、n1、n2 作為引數。
- ret := 0
- 當 n1 <= nax 時，執行以下操作：
- ret := ret + min(nax + 1, n2 – n1)
- n1 := n1 * 10
- n2 := n2 * 10
- 返回 ret
讓我們看下面的實現來更好地理解：
示例
#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
更新於: 2020-06-01
722 次瀏覽
廣告