diff options
Diffstat (limited to 'kth_smallest_lexicographical.cpp')
-rw-r--r-- | kth_smallest_lexicographical.cpp | 48 |
1 files changed, 18 insertions, 30 deletions
diff --git a/kth_smallest_lexicographical.cpp b/kth_smallest_lexicographical.cpp index 1e292ec..71478e9 100644 --- a/kth_smallest_lexicographical.cpp +++ b/kth_smallest_lexicographical.cpp @@ -1,43 +1,31 @@ +// 440. K-th Smallest in Lexicographical Order #include "leetcode.h" +// given two integers 'n' and 'k', return the k'th lexicographically smallest +// integer class Soltuion { public: int findKthNumber(int n, int k) { - int ans = 0, rankNum = 0, next = 0, rankNext = 0; - while (rankNum != k) { - int lower = ans ? 0 : 1, upper = 9; - while (lower < upper) { - auto mid = (lower + upper + 1) / 2; - next = ans * 10 + mid; - rankNext = rank(next, n); + int curr = 1; + for (--k; k > 0;) { + int cnt = 0; + for (long long first = static_cast<long long>(curr), last = first + 1; + first <= n; first *= 10, last *= 10) + cnt += static_cast<int>((min(n + 1LL, last) - first)); + if (k >= cnt) { + ++curr; + k -= cnt; + } else { + curr *= 10; + --k; } - ans *= 10, ans += lower; - rankNum = (ans == next ? rankNext : rank(ans, n)); } - return ans; - } - -private: - static int rank(int prefix, int maxVal) { - int ret = 1, num = 0; - for (int i = prefix; i; i /= 10, ++num) - for (int j = 1; j <= i % 10; ++j) - ret += numPrefixes(i - j, maxVal); - ret += num - 1; - return ret; - } - static int numPrefixes(int prefix, int maxVal) { - if (prefix == 0) - return 0; - int ret = 0; - unsigned long long ull = 1; - for (unsigned long long val = prefix; val <= maxVal; ull *= 10, val *= 10) - ret += min(ull, maxVal - val + 1); - return ret; + return curr; } }; int main() { Soltuion obj; - cout << obj.findKthNumber(13, 2); + printf("%d\n", obj.findKthNumber(13, 2)); // expect: 10 + printf("%d\n", obj.findKthNumber(1, 1)); // expect: 1 } |