[9/22] 1~n字典序的第k個

16th鐵人賽

歐噴禿沃可

團隊晶心壯士III: ALcHemist

2024-09-22 23:37:23

141 瀏覽

分享至

昨天的10969

演唱歌單中，最愛的歌是カラス，分享給大家
僕は何で悲しくも　この時代に生まれてきたんだろう
自分すら制御できず
まるで飛び方を忘れてるカラス
https://youtu.be/AGrt2_EWW4A?si=pDLSVAOXvJH8dihG

2024/09/22 Leetcode Daily Problem

440. K-th Smallest in Lexicographical Order

題意

給定一整數n與k，求1~n按字典序排列的第k個。
難度: 難，難以理解的難

思路1

第一招，當然是把昨天的題386. Lexicographical Numbers拿出來稍加修改送出。
昨天的講解傳送門: [9/21] 字典序生成器，是在O(N)內生成1~N的字典序排列。

實作1

class Solution {
public:
    int findKthNumber(int n, int k) {
        vector<int> order;

        stack<int> st;
        for (int i = 9; i >= 1; i--)
            st.push(i);

        // DFS
        while (!st.empty())
        {
            int curr = st.top();
            st.pop();
            if (curr <= n)
            {
                order.push_back(curr);
                if((int)order.size() == k)
                    return curr;
            }

            curr *= 10;
            if (curr <= n)
            {
                // Add new children
                for (int i = 9; i >= 0; i--)
                    if ((curr + i) <= n)
                        st.push(curr + i);
            }
        }
        
        return -1;
    }
};

結果1

Time Limit Exceeded 40 / 69 test cases passed.
input: 681692778 351251360
看來O(N)還不夠快...

思路2

參考網路大神的精闢拆解，如果今天是1~無限大，字典序可以按照十元樹(一個根有十個孩子)生成:

1 -> 10 -> 100 -> 1000 -> ...
        -> 101
        -> 102
        -> ...
        -> 109
  -> 11 -> 110
        -> 111
        -> 112
        -> ...
  -> 12 -> 120
        -> 121
        -> 122
        ...
  ...   ...
  -> 19 -> 190
        -> 191
        ...
2 -> 20 -> 200 ...
        -> 201
        ...
  ...
3 ->    ...
...

而限縮在1~N的字典序，則相當於把所有節點大於N的子樹全部砍掉。

而求第k個，可以一個位數一個位數來觀察。
在完整的字典序排列中，只有1位數的排列會長這樣:
1, 10, 100, ..., 2, ..., 3, ...
只有2位數的排列會長這樣:
..., 10, 100, ..., 11, ..., 12, ...
也就是說，對於兩個相鄰的數a與a+1，我們要算出他們的字典序之間夾雜了多少數!
因為當a與a+1中，大於N的子樹全部砍掉，我們可以算出到a+1之前共經歷了多少數。

實作2

find_gap:
檢查相鄰兩數a, a+1之間夾雜了多少數小於N。
若a還沒超過N，則持續增加檢查位數。
舉例:
find_gap(N, 1, 2)會計算以下區間夾雜的數量
1 ~ 2
10 ~ 20
1000 ~ 2000
10000 ~ 20000
直到a超過N為止

findKthNumber:
從1開始指定相鄰的1位數下去查夾雜了多少數。
若算出來的累計gap已達指定k值，則代表steps就是第k個字典序。
若不是則累計gap，往下一個相鄰的1位數檢查。

class Solution
{
private:
    // Find steps from a to a + 1
    int find_gap(const long long n, long long a, long long b)
    {
        int steps = 0;
        while (a <= n)
        {
            // cout << "between " << a << " and " << b << " have " << min(n + 1, b) - a << " steps" << endl;
            // If a < n < b, gap is n - a + 1 steps (a, a + 1, ... n)
            // Else if a < b < n, gap is b - a steps (a, a + 1, ... b - 1)
            steps += min(n + 1, b) - a;
            a *= 10;
            b *= 10;
        }
        return steps;
    }

public:
    int findKthNumber(int n, int k)
    {
        int steps = 1;
        k--;

        while (k)
        {
            int gap = find_gap((long long)n, (long long)steps, (long long)steps + 1);
            if (gap <= k)
            {
                k -= gap;
                steps++;
            }
            else
            {
                k--;
                steps *= 10;
            }
        }

        return steps;
    }
};

結果2

Accepted
69/69 cases passed (7 ms)
Your runtime beats 21.51 % of cpp submissions
Your memory usage beats 54.58 % of cpp submissions (7.5 MB)

這題真的很難，提供測資[681692778, 351251360]印出來的檢查順序供參考:

between 1 and 2 have 1 steps
between 10 and 20 have 10 steps
between 100 and 200 have 100 steps
between 1000 and 2000 have 1000 steps
between 10000 and 20000 have 10000 steps
between 100000 and 200000 have 100000 steps
between 1000000 and 2000000 have 1000000 steps
between 10000000 and 20000000 have 10000000 steps
between 100000000 and 200000000 have 100000000 steps
between 2 and 3 have 1 steps
between 20 and 30 have 10 steps
between 200 and 300 have 100 steps
between 2000 and 3000 have 1000 steps
between 20000 and 30000 have 10000 steps
between 200000 and 300000 have 100000 steps
between 2000000 and 3000000 have 1000000 steps
between 20000000 and 30000000 have 10000000 steps
between 200000000 and 300000000 have 100000000 steps
between 3 and 4 have 1 steps
between 30 and 40 have 10 steps
between 300 and 400 have 100 steps
between 3000 and 4000 have 1000 steps
between 30000 and 40000 have 10000 steps
between 300000 and 400000 have 100000 steps
between 3000000 and 4000000 have 1000000 steps
between 30000000 and 40000000 have 10000000 steps
between 300000000 and 400000000 have 100000000 steps
between 4 and 5 have 1 steps
between 40 and 50 have 10 steps
between 400 and 500 have 100 steps
between 4000 and 5000 have 1000 steps
between 40000 and 50000 have 10000 steps
between 400000 and 500000 have 100000 steps
between 4000000 and 5000000 have 1000000 steps
between 40000000 and 50000000 have 10000000 steps
between 400000000 and 500000000 have 100000000 steps
between 40 and 41 have 1 steps
between 400 and 410 have 10 steps
between 4000 and 4100 have 100 steps
between 40000 and 41000 have 1000 steps
between 400000 and 410000 have 10000 steps
between 4000000 and 4100000 have 100000 steps
between 40000000 and 41000000 have 1000000 steps
between 400000000 and 410000000 have 10000000 steps
between 41 and 42 have 1 steps
between 410 and 420 have 10 steps
between 4100 and 4200 have 100 steps
between 41000 and 42000 have 1000 steps
between 410000 and 420000 have 10000 steps
between 4100000 and 4200000 have 100000 steps
between 41000000 and 42000000 have 1000000 steps
between 410000000 and 420000000 have 10000000 steps
between 410 and 411 have 1 steps
between 4100 and 4110 have 10 steps
between 41000 and 41100 have 100 steps
between 410000 and 411000 have 1000 steps
between 4100000 and 4110000 have 10000 steps
between 41000000 and 41100000 have 100000 steps
between 410000000 and 411000000 have 1000000 steps
between 411 and 412 have 1 steps
between 4110 and 4120 have 10 steps
between 41100 and 41200 have 100 steps
between 411000 and 412000 have 1000 steps
between 4110000 and 4120000 have 10000 steps
between 41100000 and 41200000 have 100000 steps
between 411000000 and 412000000 have 1000000 steps
between 412 and 413 have 1 steps
between 4120 and 4130 have 10 steps
between 41200 and 41300 have 100 steps
between 412000 and 413000 have 1000 steps
between 4120000 and 4130000 have 10000 steps
between 41200000 and 41300000 have 100000 steps
between 412000000 and 413000000 have 1000000 steps
between 413 and 414 have 1 steps
between 4130 and 4140 have 10 steps
between 41300 and 41400 have 100 steps
between 413000 and 414000 have 1000 steps
between 4130000 and 4140000 have 10000 steps
between 41300000 and 41400000 have 100000 steps
between 413000000 and 414000000 have 1000000 steps
between 414 and 415 have 1 steps
between 4140 and 4150 have 10 steps
between 41400 and 41500 have 100 steps
between 414000 and 415000 have 1000 steps
between 4140000 and 4150000 have 10000 steps
between 41400000 and 41500000 have 100000 steps
between 414000000 and 415000000 have 1000000 steps
between 415 and 416 have 1 steps
between 4150 and 4160 have 10 steps
between 41500 and 41600 have 100 steps
between 415000 and 416000 have 1000 steps
between 4150000 and 4160000 have 10000 steps
between 41500000 and 41600000 have 100000 steps
between 415000000 and 416000000 have 1000000 steps
between 416 and 417 have 1 steps
between 4160 and 4170 have 10 steps
between 41600 and 41700 have 100 steps
between 416000 and 417000 have 1000 steps
between 4160000 and 4170000 have 10000 steps
between 41600000 and 41700000 have 100000 steps
between 416000000 and 417000000 have 1000000 steps
between 4160 and 4161 have 1 steps
between 41600 and 41610 have 10 steps
between 416000 and 416100 have 100 steps
between 4160000 and 4161000 have 1000 steps
between 41600000 and 41610000 have 10000 steps
between 416000000 and 416100000 have 100000 steps
between 4161 and 4162 have 1 steps
between 41610 and 41620 have 10 steps
between 416100 and 416200 have 100 steps
between 4161000 and 4162000 have 1000 steps
between 41610000 and 41620000 have 10000 steps
between 416100000 and 416200000 have 100000 steps
between 41610 and 41611 have 1 steps
between 416100 and 416110 have 10 steps
between 4161000 and 4161100 have 100 steps
between 41610000 and 41611000 have 1000 steps
between 416100000 and 416110000 have 10000 steps
between 41611 and 41612 have 1 steps
between 416110 and 416120 have 10 steps
between 4161100 and 4161200 have 100 steps
between 41611000 and 41612000 have 1000 steps
between 416110000 and 416120000 have 10000 steps
between 41612 and 41613 have 1 steps
between 416120 and 416130 have 10 steps
between 4161200 and 4161300 have 100 steps
between 41612000 and 41613000 have 1000 steps
between 416120000 and 416130000 have 10000 steps
between 416120 and 416121 have 1 steps
between 4161200 and 4161210 have 10 steps
between 41612000 and 41612100 have 100 steps
between 416120000 and 416121000 have 1000 steps
between 416121 and 416122 have 1 steps
between 4161210 and 4161220 have 10 steps
between 41612100 and 41612200 have 100 steps
between 416121000 and 416122000 have 1000 steps
between 416122 and 416123 have 1 steps
between 4161220 and 4161230 have 10 steps
between 41612200 and 41612300 have 100 steps
between 416122000 and 416123000 have 1000 steps
between 416123 and 416124 have 1 steps
between 4161230 and 4161240 have 10 steps
between 41612300 and 41612400 have 100 steps
between 416123000 and 416124000 have 1000 steps
between 416124 and 416125 have 1 steps
between 4161240 and 4161250 have 10 steps
between 41612400 and 41612500 have 100 steps
between 416124000 and 416125000 have 1000 steps
between 416125 and 416126 have 1 steps
between 4161250 and 4161260 have 10 steps
between 41612500 and 41612600 have 100 steps
between 416125000 and 416126000 have 1000 steps
between 416126 and 416127 have 1 steps
between 4161260 and 4161270 have 10 steps
between 41612600 and 41612700 have 100 steps
between 416126000 and 416127000 have 1000 steps
between 4161260 and 4161261 have 1 steps
between 41612600 and 41612610 have 10 steps
between 416126000 and 416126100 have 100 steps
between 4161261 and 4161262 have 1 steps
between 41612610 and 41612620 have 10 steps
between 416126100 and 416126200 have 100 steps
between 4161262 and 4161263 have 1 steps
between 41612620 and 41612630 have 10 steps
between 416126200 and 416126300 have 100 steps
between 41612620 and 41612621 have 1 steps
between 416126200 and 416126210 have 10 steps
between 41612621 and 41612622 have 1 steps
between 416126210 and 416126220 have 10 steps
between 416126210 and 416126211 have 1 steps
between 416126211 and 416126212 have 1 steps
between 416126212 and 416126213 have 1 steps
between 416126213 and 416126214 have 1 steps
between 416126214 and 416126215 have 1 steps
between 416126215 and 416126216 have 1 steps
between 416126216 and 416126217 have 1 steps
between 416126217 and 416126218 have 1 steps
between 416126218 and 416126219 have 1 steps
416126219