文章目錄

• 前言
• 一、大數(shù)問題
• 二、問題分析
• 總結(jié)

成都網(wǎng)站設(shè)計(jì)、成都網(wǎng)站建設(shè)介紹好的網(wǎng)站是理念、設(shè)計(jì)和技術(shù)的結(jié)合。創(chuàng)新互聯(lián)公司擁有的網(wǎng)站設(shè)計(jì)理念、多方位的設(shè)計(jì)風(fēng)格、經(jīng)驗(yàn)豐富的設(shè)計(jì)團(tuán)隊(duì)。提供PC端+手機(jī)端網(wǎng)站建設(shè)，用營銷思維進(jìn)行網(wǎng)站設(shè)計(jì)、采用先進(jìn)技術(shù)開源代碼、注重用戶體驗(yàn)與SEO基礎(chǔ)，將技術(shù)與創(chuàng)意整合到網(wǎng)站之中，以契合客戶的方式做到創(chuàng)意性的視覺化效果。

---

前言

貪心法

---

提示：以下是本篇文章正文內(nèi)容，下面案例可供參考

一、大數(shù)問題

給定一組非負(fù)整數(shù) nums，重新排列每個(gè)數(shù)的順序（每個(gè)數(shù)不可拆分）使之組成一個(gè)大的整數(shù)。

注意：輸出結(jié)果可能非常大，所以你需要返回一個(gè)字符串而不是整數(shù)。

二、問題分析

這道題目本質(zhì)上是考察排序

很多人覺著這道題可以通過直接將輸入數(shù)組 nums 降序排列，然后按照順序?qū)⑺械臄?shù)字拼成字符串就可以了，這種思路實(shí)際上是不對(duì)的。

我們使用數(shù)組 [3,30,34,5,9] 來說明上面的思路為什么不對(duì)：

• 對(duì)數(shù)組排序后的數(shù)組：[34,30,9,5,3]
• 然后按照順序輸出為字符串：“3430953”

很明顯這個(gè)字符串并不是大的，因?yàn)榇蟮淖址隙ㄒ?9 開頭

否定了上面的思路，你可能會(huì)相處另一個(gè)錯(cuò)誤的思路：那就是先按照每個(gè)元素?cái)?shù)字的第一位進(jìn)行降序排列

這樣第一位大的數(shù)字是排前面的，但是如果第一位相等，第二位數(shù)字大的可能會(huì)排在后面了，那就不是大值了，比如示例中的3，30，34.

要解決這個(gè)題目是有一個(gè)技巧的，就是排序的條件和正常的不太一樣。我們看給一個(gè)數(shù)組進(jìn)行排序的時(shí)候，只需要比較兩個(gè)元素 (假設(shè) x 和 y 是數(shù)組的任意兩個(gè)元素) 的大小即可：

• 只要 x >y，那么降序排列的話 y 就應(yīng)該排在 x 的后面
• 只要 x< y，那么降序排列的話 x 就應(yīng)該排在 y 的后面

對(duì)于這道題目，假設(shè) x 和 y 是數(shù)組中任意兩個(gè)元素，那么 x 是需要排在 y 的前面還是后面呢？這個(gè)取決于 xy 和 yx 哪個(gè)大哪個(gè)?。?/p>

• 如果 xy >yx，那么 y 應(yīng)該排在 x 的后面
• 如果 xy< yx，那么 x 應(yīng)該排在 y 的后面
  比如，x = 30， y = 3，那么 xy = 303，yx = 330，因?yàn)?xy< yx ，所以 30 應(yīng)該在排在 3 的后面，這樣就可以得到大值。

---

總結(jié)

代碼及運(yùn)行結(jié)果：

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("輸入數(shù)組：");
		Scanner scanner = new Scanner(System.in);
		String srcString = scanner.next().toString();
		String[] sr = srcString.split(",");

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

}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)站名稱：Java-最大數(shù)問題-創(chuàng)新互聯(lián)
分享鏈接：http://weahome.cn/article/gcdph.html