引言

最近，有位大神同学在到处面试，在群里抛出了一些面试题，于是有了这篇文章，对排序算法的一次复习。

问题

大神同学遇到的问题，来源于179. Largest Number，本人还是习惯英文版（刷题在两年前。。。）。

Given a list of non negative integers, arrange them such that they form the largest number.
Example 1:
Input: [10,2]
Output: "210"

解题思路

• 可以把这个问题看成是一个排序问题，毕竟是通过不同的数字排列来获取最优解的， 那么谁在前，谁在后呢？

210 > 102
2 * 10^2 + 10 > 10 * 10 + 2

• 可以得出， 与 的比较，前者大，则a排在前面，后者大则b排在前面。

排序算法的选择

快速排序的变形

• 时间复杂度平均为，当然最坏情况是，与测试用例强相关。

class Solution {
    public String largestNumber(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        StringBuilder max = new StringBuilder();
        for (int num : nums) {
            // 特殊情况的处理
            if (nums[0] == 0) {
                return "0";
            } else {
                max.append(num);
            }
        }
        return max.toString();
    }

   private static void quickSort(int[] nums, int low, int high) {

        if (low < high) {
            int index = getIndex(nums, low, high);
            if (index == -1) {
                return;
            }
            quickSort(nums, low, index - 1);
            quickSort(nums, index + 1, high);
        }
    }

    private static int  getIndex(int[] nums, int low, int high) {
        int flag = nums[low];
        boolean isZero = true;
        while (low < high) {
            while (low < high && compareNum(flag, nums[high]) >= 0) {
                if (nums[high] != 0) {
                    isZero = false;
                }
                high --;
            }

            nums[low] = nums[high];

            while (low < high && compareNum(nums[low], flag) >= 0) {
                if (nums[low] != 0) {
                    isZero = false;
                }
                low++;
            }

            nums[high] = nums[low];

        }
        nums[low] = flag;
        // 全是0 只扫描一次
        if (isZero) {
            return -1;
        }
        return low;
    }
}

• Arrays.sort排序，使用TimSort，时间复杂度最好情况为，平均情况为，实现方式为自定义Comparator。

class Solution {
    public String largestNumber(int[] nums) {

        List<Integer> list = new ArrayList<>();
        for (int num : nums) {
            list.add(num);
        }
        // TimSort
        list.sort(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return compareNum(o1, o2);
            }
        });
        StringBuilder max = new StringBuilder();
        for (int num : list) {
            if (list.get(0) == 0) {
                return "0";
            } else {
                max.append(num);
            }
        }
        return max.toString();
    }

    private static int compareNum(int a, int b) {

        String str1 = String.valueOf(a);
        String str2 = String.valueOf(b);
        int len1 = str1.length();
        int len2 = str2.length();
        double sum1 = Math.pow(10, len2) * a + b;
        double sum2 = Math.pow(10, len1) * b + a;
        if (sum2 > sum1) {
            return 1;
        } else if (sum1 > sum2) {
            return -1;
        } else {
            return 0;
        }
    }
}

结语

说明算法实在不是笔者的强项，而且TimSort原理也在学习中。

参考文献

https://leetcode-cn.com/problems/largest-number/
https://sikasjc.github.io/2018/07/25/timsort/#%E6%A6%82%E8%BF%B0