AC 200ms c++ solution, beats 98%


  • 34
    class Solution {
    public:
        vector<int> lexicalOrder(int n) {
            vector<int> res(n);
            int cur = 1;
            for (int i = 0; i < n; i++) {
                res[i] = cur;
                if (cur * 10 <= n) {
                    cur *= 10;
                } else {
                    if (cur >= n) 
                        cur /= 10;
                    cur += 1;
                    while (cur % 10 == 0)
                        cur /= 10;
                }
            }
            return res;
        }
    };
    

  • 0
    D

    Brilliant solution, Thanks


  • 0
    T

    Excellent solution. Thanks


  • 1
    S

    @withacup So clever!


  • 0
    S

    @withacup Can you explian:

    while (cur % 10 == 0)
    cur /= 10; ?


  • 3

    @sangshuhao7
    Thanks for your reply!
    To calculate the next lexicographical number for any number X, there is only two scenarios to consider:

    • If we can add a trailing zero to it, then the next number is X * 10, because X * 10 is always the lexicographically smallest number bigger than X.
    • If X * 10 is bigger than the given number n, then the next smallest number can be generated by increasing X's least significant digit by 1. We have two sub-scenarios under this particular situation:
      • If X == n, then X + 1 is bigger than n, we need increase the second least significant digit in X, so we have if(cur == n) cur /= 10;
      • After we increased the number, we still need to take care another problem:
        • If the increased number has no trailing zeros, we can safely add it to result.
        • Otherwise we need to get rid of the trailing zeros, the reason is:
          If the increased number has trailing zero/zeros, that mean we are actually increasing the digit right before the trailing zero
          E.g. the next number to 1999 is 2, not 2000, because by adding 1 to the least significant digit, the first digit in 1999, which is the most significant digit, changed into 2.

  • 0
    L

    Clever solution. Thank you !


Log in to reply
 

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