diff options
author | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
---|---|---|
committer | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
commit | d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch) | |
tree | 96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /kth_smallest_lexicographical.cpp | |
download | leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip |
initial
Diffstat (limited to 'kth_smallest_lexicographical.cpp')
-rw-r--r-- | kth_smallest_lexicographical.cpp | 43 |
1 files changed, 43 insertions, 0 deletions
diff --git a/kth_smallest_lexicographical.cpp b/kth_smallest_lexicographical.cpp new file mode 100644 index 0000000..1e292ec --- /dev/null +++ b/kth_smallest_lexicographical.cpp @@ -0,0 +1,43 @@ +#include "leetcode.h" + +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); + } + 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; + } +}; + +int main() { + Soltuion obj; + cout << obj.findKthNumber(13, 2); +} |