剑指 Offer 45. 把数组排成最小的数

QuickSort

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public String minNumber(int[] nums) {
        List<String> numList = new ArrayList<>(nums.length);
        for (int num : nums) {
            numList.add(String.valueOf(num));
        }

        numList.sort((o1, o2) -> (o1 + o2).compareTo(o2 + o1));

        return String.join("", numList);
    }
}

QuickSort

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
class Solution {
    public String minNumber(int[] nums) {
        List<String> numList = new ArrayList<>(nums.length);
        for (int num : nums) {
            numList.add(String.valueOf(num));
        }

        quickSort(numList, 0, numList.size() - 1);

        return String.join("", numList);
    }

    private void quickSort(List<String> numList, int i, int j) {
        if (i >= j) {
            return;
        }

        int pivotIndex = partition(numList, i, j);
        quickSort(numList, i, pivotIndex - 1);
        quickSort(numList, pivotIndex + 1, j);
    }

    private int partition(List<String> numList, int i, int j) {
        int pivotIndex = i + ThreadLocalRandom.current().nextInt(j - i + 1); // i + [0, j - i] -> [i, j]
        String pivotValue = numList.get(pivotIndex);
        swap(numList, pivotIndex, i);
        int index = i;
        for (int k = i + 1; k <= j; k++) {
            if (lessThan(numList.get(k), pivotValue)) {
                swap(numList, k, ++index);
            }
        }

        swap(numList, index, i);
        return index;
    }

    private boolean lessThan(String a, String b) {
        return (a + b).compareTo(b + a) < 0;
    }

    private void swap(List<String> numList, int i, int j) {
        String tmp = numList.get(i);
        numList.set(i, numList.get(j));
        numList.set(j, tmp);
    }
}

QuickSort

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
55
56
57
58
59
class Solution {
    public String minNumber(int[] nums) {
        sort(nums, 0, nums.length - 1);
        StringBuilder sb = new StringBuilder();
        for (int num : nums) {
            sb.append(num);
        }
        return sb.toString();
    }

    private void sort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }

        int pivotIndex = partition(nums, left, right);
        sort(nums, left, pivotIndex - 1);
        sort(nums, pivotIndex + 1, right);
    }

    private int partition(int[] nums, int left, int right) {
        int pivotIndex = left + ThreadLocalRandom.current().nextInt(right - left + 1);
        int pivotValue = nums[pivotIndex];
        swap(nums, left, pivotIndex);

        int index = left;
        for (int i = left + 1; i <= right; i++) {
            if (lessThan(nums[i], pivotValue)) {
                swap(nums, i, ++index);
            }
        }

        swap(nums, left, index);
        return index;
    }

    private boolean lessThan(int x, int y) {
        // xy < yx
        long tmp = 10;
        while (tmp <= y) {
            tmp *= 10;
        }
        long a = x * tmp + y;

        tmp = 10;
        while (tmp <= x) {
            tmp *= 10;
        }
        long b = y * tmp + x;

        return a < b;
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

References

剑指 Offer 45. 把数组排成最小的数