Java-最大数问题-创新互联

• 前言
• 一、大数问题
• 二、问题分析
• 总结

贪心法

提示：以下是本篇文章正文内容，下面案例可供参考

给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个大的整数。

注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。

这道题目本质上是考察排序

很多人觉着这道题可以通过直接将输入数组 nums 降序排列，然后按照顺序将所有的数字拼成字符串就可以了，这种思路实际上是不对的。

我们使用数组 [3,30,34,5,9] 来说明上面的思路为什么不对：

• 对数组排序后的数组：[34,30,9,5,3]
• 然后按照顺序输出为字符串：“3430953”

很明显这个字符串并不是大的，因为大的字符串肯定要以 9 开头

否定了上面的思路，你可能会相处另一个错误的思路：那就是先按照每个元素数字的第一位进行降序排列

这样第一位大的数字是排前面的，但是如果第一位相等，第二位数字大的可能会排在后面了，那就不是大值了，比如示例中的3，30，34.

要解决这个题目是有一个技巧的，就是排序的条件和正常的不太一样。我们看给一个数组进行排序的时候，只需要比较两个元素 (假设 x 和 y 是数组的任意两个元素) 的大小即可：

• 只要 x >y，那么降序排列的话 y 就应该排在 x 的后面
• 只要 x< y，那么降序排列的话 x 就应该排在 y 的后面

对于这道题目，假设 x 和 y 是数组中任意两个元素，那么 x 是需要排在 y 的前面还是后面呢？这个取决于 xy 和 yx 哪个大哪个小：

• 如果 xy >yx，那么 y 应该排在 x 的后面
• 如果 xy< yx，那么 x 应该排在 y 的后面
  比如，x = 30， y = 3，那么 xy = 303，yx = 330，因为 xy< yx ，所以 30 应该在排在 3 的后面，这样就可以得到大值。

代码及运行结果：

package max;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class MaxNum {public static String largestNumber(String[] strs) {// 降序排列
		Arrays.sort(strs, new Comparator() {	@Override
			public int compare(String x, String y) {		String xy = x + y;
				String yx = y + x;
				return yx.compareTo(xy);
			}
		});

		if (strs[0] == "0")
			return ""; // "00000"

		StringBuilder sb = new StringBuilder();
		for (String num : strs) {	sb.append(num);
		}
		return sb.toString();
	}

	public static void main(String[] args) {// TODO Auto-generated method stub
		System.out.println("输入数组：");
		Scanner scanner = new Scanner(System.in);
		String srcString = scanner.next().toString();
		String[] sr = srcString.split(",");

		String result = largestNumber(sr);
		System.out.println(result);
	}

}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧