算法:字典序排序

算法 About 1,494 words

题目

给定一个整数n,返回从1n的字典顺序。

示例

给定n=13,返回[1,10,11,12,13,2,3,4,5,6,7,8,9]

请尽可能的优化算法的时间复杂度和空间复杂度。 输入的数据n小于等于5,000,000

方法一

转成String后使用Stringcompare方法,再转回Integer

public List<Integer> lexicalOrder(int n) {
    ArrayList<String> list = new ArrayList<>();
    for (int i = 1; i <= n; i++) {
        list.add(String.valueOf(i));
    }
    Collections.sort(list);

    ArrayList<Integer> integers = new ArrayList<>();
    for (String s : list) {
        integers.add(Integer.valueOf(s));
    }
    return integers;
}

执行用时:27 ms, 在所有Java提交中击败了20.16%的用户 内存消耗:44.3 MB, 在所有Java提交中击败了41.82%的用户

方法二

数字1进入dfs递归后,判断不大于n则加入List,再对1乘以10后,对1119做递归判断,如果大于n则跳出递归,不大于则11再乘以10`继续递归。

数字29以此类推。

public List<Integer> lexicalOrder2(int n) {
    List<Integer> list = new ArrayList<>(n);
    for (int i = 1; i <= 9; i++) {
        // list=empty, n=13, i=1
        dfs(list, n, i);
    }
    return list;
}

public boolean dfs(List<Integer> list, int n, int target) {
    // target=1 < n=13
    if (target > n) {
        return false;
    }
    // list={1}
    list.add(target);

    // target=10
    target *= 10;

    // 10 11 12 ... 19
    for (int i = 0; i <= 9; i++) {
        // list={1}, n=13, target+i=10+1=11
        if (!dfs(list, n, target + i)) {
            break;
        }
    }
    return true;
}

执行用时:3 ms, 在所有Java提交中击败了85.44%的用户 内存消耗:44.4 MB, 在所有Java提交中击败了33.65%的用户

LeetCode 原题地址

https://leetcode-cn.com/problems/lexicographical-numbers

Views: 2,366 · Posted: 2021-02-28

————        END        ————

Give me a Star, Thanks:)

https://github.com/fendoudebb/LiteNote

扫描下方二维码关注公众号和小程序↓↓↓

扫描下方二维码关注公众号和小程序↓↓↓


Today On History
Browsing Refresh