未分類

Largest Number

Go, LeetCode, Sort

Largest Number

Given a list of non negative integers, arrange them such that they form the largest number.

For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

提示 解題應用
Sort 規律觀查

Default:

1
2
3
func largestNumber(nums []int) string {
}

解答思路:

這題最主要是要將陣列的元素按特定規律做排序，仔細觀查會發現不管幾位數，只要開頭數字誰大就表示誰要放在最前面，不過萬一碰到像[3,30]與[3,34]的話呢?這時只要把各自的元素放到對方後頭就可以比較了，像前面的例子會變成[330,303]與[334,343]，誰比較大誰該擺前面便馬上一目瞭然了，最做golang做排序會呼叫Len(),Swap(),Less()三個function做排序，只要針對Less()將比較的部分複寫成要的規則，最後在排序之後就會變成能組出最大值順序的結果。

程式碼解說:

因為這次需要複寫成要的排序規則以組出最大值，注意在排序之前會先將原本陣列的數字全轉為字串，所以後續的比較全都是字串的比較，一開始便需要定義Len(),Swap(),Less()三個function，前面兩個function與一般排序規則並無差別，而主要複寫的便是Less()的比較，如思路所述每次都將各自的元素放到另一方後頭才開始比較，所以在兩兩元素都為字串的情況下便很容易得到兩個互相組合的字串，接著就開始一個個字元比較rune值以判斷index為i的元素是否真的比j小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
type Number []string
func (a Number) Len() int          { return len(a) }
func (a Number) Swap(i int, j int) { a[i], a[j] = a[j], a[i] }
func (a Number) Less(i int, j int) bool {
	var char rune
	ij := a[i] + a[j]
	ji := a[j] + a[i]
	for i, v := range ij {
		char = rune(ji[i])
		if v < char {
			return true
		} else if v > char {
			return false
		}
	}
	return false
}

定義好排序規則之後剩下就是處理進來的資料，由於定義的排序規則是以字串來處理資料的比較，就要先產生一個一模一樣長度的陣列，再利用迴圈遍歷一個個將元素轉為字串放入對應的陣列位置之中，全數資料轉換為字串陣列後就開始照先前定義的規則做排序，排序的結果是由小排至大(開頭數字大的在後面)，所以每次取出字串都要將其放入結果字串的開頭，最後為了要避免陣列只有0的值而組出”000”的結果，要一邊檢查是否有非0的元素存在，如果元素皆為0的時候只要回傳一個”0”即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func largestNumber(nums []int) string {
	var result string
	allzero := true
	strNum := make([]string, len(nums))
	for i, v := range nums {
		strNum[i] = strconv.Itoa(v)
	}
	sort.Sort(Number(strNum))
	for _, v := range strNum {
		if v != "0" {
			allzero = false
		}
		result = v + result
	}
	if allzero {
		return "0"
	}
	return result
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
type Number []string
func (a Number) Len() int          { return len(a) }
func (a Number) Swap(i int, j int) { a[i], a[j] = a[j], a[i] }
func (a Number) Less(i int, j int) bool {
	var char rune
	ij := a[i] + a[j]
	ji := a[j] + a[i]
	for i, v := range ij {
		char = rune(ji[i])
		if v < char {
			return true
		} else if v > char {
			return false
		}
	}
	return false
}
func largestNumber(nums []int) string {
	var result string
	allzero := true
	strNum := make([]string, len(nums))
	for i, v := range nums {
		strNum[i] = strconv.Itoa(v)
	}
	sort.Sort(Number(strNum))
	for _, v := range strNum {
		if v != "0" {
			allzero = false
		}
		result = v + result
	}
	if allzero {
		return "0"
	}
	return result
}

總結:

要將陣列中的數字盡可能組成最大值，仔細觀查會發現不管幾位數，只要開頭數字誰大就表示誰要放在最前面，萬一碰到像[3,30]與[3,34]的話，就把各自的元素放到對方後頭如[330,303]與[334,343]，誰比較大誰該擺前面便馬上一目瞭然了，最做golang做排序會呼叫Len(),Swap(),Less()三個function做排序，只要針對Less()將比較的部分複寫成要的規則，最後在排序之後就會變成能組出最大值順序的結果。

分享到