179. Largest Number

题目

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

题意

给定整型数组，求出该数字组合成最大值的字符串

例子

Input: [3,30,34,5,9]
Output: “9534330”

题解

设有x y,则当xy>yx时，我们就认为x>y；所有对于x1x2x3..xn要最大，则需要有x1>x2>x3>…>xn；所以根据上述规则重新定义比较关系，对数组进行排序，所以按排序好的顺序进行拼接就行了

代码

func largestNumber(nums []int) string {
    L := len(nums)
    if L==0{
        return ""
    }
    
    snum := make([]string,L)
    for i:=0;i<L;i++{
        snum[i]=strconv.Itoa(nums[i])
    }
    
    QuitSort(snum,0,L-1)
    res := ""
    for i:=L-1;i>=0;i--{
        res += snum[i]
    }
    for res[0]=='0'&&len(res)>1 {
        res = res[1:]
    }
    return res
    
}



// if s1>s2 return 1;when s1s2>s2>s2 that s1>s2
// The result will be 0 if s1==s2, -1 if s1 < s2, and +1 if s1 > s2.
func Compare(s1,s2 string)int{
    c1 := s1+s2
    c2 := s2+s1
    return strings.Compare(c1,c2)
}


func QuitSort(snum []string,start,end int){
    if start >= end {
        return
    }
    mid := quitSort(snum ,start,end)
    QuitSort(snum,start,mid-1)
    QuitSort(snum,mid+1,end)
}


func quitSort(snum []string,start,end int)int{
    temp := snum[start]
    
    for start<end{
        for Compare(snum[end],temp)==1&&start<end{
            end--
        }
        snum[start]=snum[end]
        for (Compare(temp,snum[start])==1||Compare(temp,snum[start])==0)&&start<end{
            start++
        }
        snum[end]=snum[start]
    }
    
    snum[start]=temp
    return start
}

总结

以前剑指offer做过，可惜没能想起来，差了以前的记录复习了一下。顺便在写了一次快排。