成都创新互联网站制作重庆分公司

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

文章目录
  • 前言
  • 一、大数问题
  • 二、问题分析
  • 总结

成都网站设计、成都网站建设介绍好的网站是理念、设计和技术的结合。创新互联公司拥有的网站设计理念、多方位的设计风格、经验丰富的设计团队。提供PC端+手机端网站建设,用营销思维进行网站设计、采用先进技术开源代码、注重用户体验与SEO基础,将技术与创意整合到网站之中,以契合客户的方式做到创意性的视觉化效果。
前言

贪心法


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

一、大数问题

给定一组非负整数 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元起,快前往官网查看详情吧


文章名称:Java-最大数问题-创新互联
分享链接:http://cxhlcq.com/article/gcdph.html

其他资讯

在线咨询

微信咨询

电话咨询

028-86922220(工作日)

18980820575(7×24)

提交需求

返回顶部