C++ O(n) Time O(1) Space Clean and Clear Solution With Explanation.


  • 0
    F

    I believe the logic is clear enough without a long paragraph of explanation. But in case you are still confused, I added some explanation:

    class Solution {
        int next(int last, int n)
        {
            if (last * 10 <= n)
                return last * 10;
            if (last == n)
                last /= 10;
            ++last;
            while(last % 10 == 0)
                last /= 10;
            return last;
        }
    public:
        vector<int> lexicalOrder(int n) {
            if (n < 1) return vector<int>();
            vector<int> result(n);
            result[0] = 1;
            for (int i = 1; i < n; ++ i)
                result[i] = next(result[i - 1], n);
            return result;
        }
    };
    

    Explanation:
    Basically, there are only 4 situations: (or 4 rules to generate next number, depending on n and i )
    A: Suppose n = 30
    ...17,18, 19, 2, 20, ..
    ....................i...i+1.....
    B: Suppose n = 30
    ...17,18, 19, 2, 20,..
    ...............i...i+1.....
    C:Suppose n = 14
    ...12,13, 14, 2, 3, 4 ..
    ................i..i+1.....
    D:Suppose n = 14
    ...12,13, 14, 2, 3, 4 ..
    ...i....i+1......................

    The "next" function is just an implementation of checking which situation it is now and generate the next number accordingly.


  • 0
    S

    @fentoyal what is the name of the algorithm you are using here? Could you explain the logic behind your solution?


  • 1
    F

    @sri_hari
    The algorithm's name is "Fentoyal's algorithm".
    ...
    I was kidding.
    It doesn't have a name. It's just some logic I came up with. The idea is easy. Generate next (using "next" function) number based on the last number, one by one. As for "how", just ask yourself, if you are at index i, what are all possible values for i + 1? And what are the conditions for each possible value?
    Basically, there are only 4 situations: (or 4 rules to generate next number, depending on n and i )
    A: Suppose n = 30
    ...17,18, 19, 2, 20, ..
    ....................i...i+1.....
    B: Suppose n = 30
    ...17,18, 19, 2, 20,..
    ...............i...i+1.....
    C:Suppose n = 14
    ...12,13, 14, 2, 3, 4 ..
    ................i..i+1.....
    D:Suppose n = 14
    ...12,13, 14, 2, 3, 4 ..
    ...i....i+1......................


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.