386. Lexicographical Numbers

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

Given an integer n, return all the numbers in the range [1, n] sorted in lexicographical order.

You must write an algorithm that runs in O(n) time and uses O(1) extra space.

Example 1:

Input: n = 13
Output: [1,10,11,12,13,2,3,4,5,6,7,8,9]

Example 2:

Input: n = 2
Output: [1,2]

Code

lexicalOrder(150) 1,10,100,101,102,103,104,105,106,107,108,109,11,110

class Solution {
    public List<Integer> lexicalOrder(int n) {
        List<Integer> res = new ArrayList<>();
        int curr = 1;

        for(int i = 0; i < n; i++){
            res.add(curr);
            // 1 -> 10
            if(curr * 10 <= n){
                curr *= 10;
                // 100 -> 101
            }else if(curr % 10 != 9 && curr + 1 <= n){
                curr++;
            }else{
                // 192 -> 2
                if(curr == n) {
                    curr /= 10;
                }
                // 1899 -> 19, 1659 -> 166
                while(curr % 10 == 9){
                    curr /= 10;
                }
                curr += 1;
            }
        }

        return res;
    }
}