Loading...
墨滴

SuperMP

2021/04/20  阅读:41  主题:默认主题

Leetcode刷题 | 第117题:最大数

人生最糟糕的事,一个是饿肚子,一个是孤独。

179. 最大数[1]

题目:给定一组非负整数 nums,重新排列每个数的顺序(每个数不可拆分)使之组成一个最大的整数。注意:输出结果可能非常大,所以你需要返回一个字符串而不是整数。

示例 1:
输入:nums = [10,2], 输出:"210"

示例 2:
输入:nums = [3,30,34,5,9], 输出:"9534330"

示例 3:
输入:nums = [1], 输出:"1"

示例 4:
输入:nums = [10], 输出:"10"

提示:1 <= nums.length <= 100, 0 <= nums[i] <= 10^9

分析1[2]:看到求两个整数 a, b 如何拼接得到的结果更大时,就想到先转为字符串,然后比较 a + bb + a。如何比较?按字典序比较 (a + b).compareTo(y + a) 即可。

Java代码:

class Solution {
    public String largestNumber(int[] nums) {
        int n = nums.length;
        String[] s = new String[n];
        for (int i = 0; i < n; i++) {
            s[i] = Integer.toString(nums[i]);
        }
        
        Arrays.sort(s, (String x, String y) -> {
            return -(x + y).compareTo((y + x));
        });
        
        StringBuffer res = new StringBuffer();
        for (int i = 0; i < n; i++) res.append(s[i]);
        return res.charAt(0) == '0' ? "0" : res.toString();
    }
}
  • 时间复杂度为O(N*logN),即排序时间;空间复杂度为O(N),即字符数组。
  • 运行时间:>4ms

分析2[3]:快速排序 + 数学计算。

例如:a = 365, b = 3476,那么 ab = 3653476 = 3650000 + 3476ba = 3476365 = 3476000 + 365,其中 0 的个数与待拼接的数字等长

首先,给出Java版本的快速排序(快排):

private void quickSort(int[] nums, int left, int right) {
    if (left < right) {
        int pivot = nums[left];
        int idx = left; // 遍历过程中, 保持idx位置前的元素都不大于pivot
        for (int i = left + 1; i <= right; i++) {
            if (nums[i] <= pivot) { // 升序
                idx++;
                swap(nums, idx, i); // 将不大于pivot的元素依次置换到前面
            }
        }
        // 用pivot将数组划分为左小于pivot右大于pivot的两部分
        swap(nums, idx, left);
        quickSort(nums, left, idx - 1);
        quickSort(nums, idx + 1, right);
    }
}

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

其次,给出按字典序比较 a + bb + a 的快速排序代码:

private void quickSortDict(int[] nums, int left, int right) {
    if (left < right) {
        int pivot = nums[left];
        int idx = left;
        for (int i = left + 1; i <= right; i++) {
            long x = 10;
            long y = 10;
            while (nums[i] >= x) x *= 10;
            while (pivot >= y) y *= 10;
            if (nums[i] * y + pivot > pivot * x + nums[i]) { // 降序
                idx++;
                swap(nums, idx, i);
            }
        }
        swap(nums, idx, left);
        quickSortDict(nums, left, idx - 1);
        quickSortDict(nums, idx + 1, right);
    }
}

然后,给出本题Java代码:

class Solution {
    public String largestNumber(int[] nums) {
        quickSortDict(nums, 0, nums.length - 1);
        System.out.println(Arrays.toString(nums));
        
        if (nums[0] == 0return "0";
        StringBuffer stringBuffer = new StringBuffer();
        for (int num : nums) {
            stringBuffer.append(Integer.toString(num));
        }
        return stringBuffer.toString();
    }
}

最后,给出测试代码和结果:

public class Main {
    public static void main(String[] args) {
        int[] nums = {33034539};
        Solution solution = new Solution();
        String s = solution.largestNumber(nums);
        System.out.println(s);
    }
}
// [9, 5, 34, 3, 3, 30]
// 95343330
// 任选一个索引位置的元素 a 和一个更大索引位置的元素 b 拼接成的数字 ab,都不小于 ba
  • 时间复杂度为O(N*logN),即排序时间。
  • 运行时间:~2ms

参考资料

[1]

179. 最大数: https://leetcode-cn.com/problems/largest-number/

[2]

分析1: https://leetcode-cn.com/problems/largest-number/solution/fu-xue-ming-zhu-zhuan-cheng-zi-fu-chuan-mm2s6/

[3]

分析2: https://leetcode-cn.com/problems/largest-number/solution/chao-guo-100-java-shou-xie-kuai-pai-by-w-gb2w/

SuperMP

2021/04/20  阅读:41  主题:默认主题

作者介绍

SuperMP