最大数

发表于
本文字数： 2.5k 阅读时长 ≈ 2 分钟

LeetCode每日一题，179. 最大数

先看题目描述

cBKwon.png

算法和思路

排序

大致思路就是将数组里的整数都转化为字符串，构造一个字符串数组，然后对字符串数组进行排序，排序后应是降序排列，排序规则为对于字符串 a 和 b，若 a + b 的字典序小于 b + a，则将 b 排在 a 前面

算法源码

排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public String largestNumber(int[] nums) {
        int n = nums.length;
        String[] vals = new String[n];
        for (int i = 0; i < n; i++) {
            vals[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(vals, (a, b) -> (b + a).compareTo(a + b));
        StringBuilder res = new StringBuilder();
        for (String val :vals) {
            res.append(val);
        }
        if (res.charAt(0) == '0') {
            return "0";
        }
        return res.toString();
    }
}

下面是自己一开始实现的源码，忘记了可以直接使用 String 自带的方法 compareTo()，所以是手写的一个逐个字符比较的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
    public String largestNumber(int[] nums) {
        int n = nums.length;
        String[] vals = new String[n];
        for (int i = 0; i < n; i++) {
            vals[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(vals, new Comparator<String>() {
            @Override
            public int compare(String a, String b) {
                int len1 = a.length();
                int len2 = b.length();
                int len = len1 + len2;
                int index = 0;
                int i = 0; int j = 0;
                while (index < len) {
                    char c1;
                    char c2;
                    if (index < len1) {
                        c1 = a.charAt(i);
                    } else {
                        c1 = b.charAt(i);
                    }
                    if (index < len2) {
                        c2 = b.charAt(j);
                    } else {
                        c2 = a.charAt(j);
                    }
                    if (c1 != c2) {
                        return c2 - c1;
                    }
                    index++;
                    i++;
                    j++;
                    if (i == len1) {
                        i = 0;
                    }
                    if (j == len2) {
                        j = 0;
                    }
                }
                return 0;
            }
        });
        StringBuilder res = new StringBuilder();
        for (String val :vals) {
            res.append(val);
        }
        if (res.charAt(0) == '0') {
            return "0";
        }
        return res.toString();
    }
}