LeetCode 179. 最大数

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

🔥 179. 最大数

思路分析

将整数转换为字符串，然后按照以下规则排序：

如果 a + b > b + a，则 a 排在 b 前面。

如果 a + b < b + a，则 b 排在 a 前面。

如果 a + b = b + a，则 a 和 b 相对位置不变。

最后将排序后的字符串拼接起来即可。

为了得到最大的整数，我们需要对数字进行排序。排序的规则是比较两个数字 x 和 y，如果 xy（将 x 放在 y 前面）大于 yx（将 y 放在 x 前面），则 x 应该排在 y 前面。我们可以使用自定义的比较函数来实现这一点。

转换为字符串：将所有数字转换为字符串，以便进行比较。

自定义排序：使用自定义的比较函数对字符串数组进行排序，确保拼接后的结果最大。

拼接结果：将排序后的字符串数组连接成一个字符串。

处理特殊情况：如果结果的第一个字符是 ‘0’，则返回 “0”。

参考代码

type byConcat []string

func (s byConcat) Len() int {
	return len(s)
}

func (s byConcat) Less(i, j int) bool {
	return s[i]+s[j] > s[j]+s[i]
}

func (s byConcat) Swap(i, j int) {
	s[i], s[j] = s[j], s[i]
}

func largestNumber(nums []int) string {
	// 将整数转换为字符串
	strs := make([]string, len(nums))
	for i, num := range nums {
		strs[i] = strconv.Itoa(num)
	}

	// 排序
	sort.Sort(byConcat(strs))

	// 处理特殊情况
	if strs[0] == "0" {
		return "0"
	}

	// 拼接结果
	res := ""
	for _, str := range strs {
		res += str
	}
	return res
}

时间复杂度：O(n log n)，主要是排序的时间复杂度。

空间复杂度：O(n)，用于存储字符串数组。

func largestNumber(nums []int) string {
	s := make([]string, len(nums))
	for i := 0; i < len(nums); i++ {
		s[i] = strconv.Itoa(nums[i])
	}
	sort.SliceStable(s, func(i, j int) bool {
		return s[i]+s[j] > s[j]+s[i]
	})
	if s[0] == "0" {
		return "0"
	}
	return strings.Join(s, "")
}

🍏 点击查看 Java 题解

class Solution {
    public String largestNumber(int[] nums) {
        String[] strs = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            strs[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(strs, (o1, o2) -> (o2 + o1).compareTo(o1 + o2));
        String res = String.join("", strs);
        if (res.charAt(0) == '0') {
            return "0";
        }
        return res;
    }
}

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/33217980