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.

解题思路：

自定义一种排序规则，然后对原数组排序即可。最开始我想逐个字符分析来排序规则，发觉太麻烦了，考虑的东西太多。对于字符串s1和s2，判断s1>s2只需要s1s2>s2s1即可，结果驱动型。

注意若参数为0,0，最终结果为0。

另外，整数转字符串的方法有没有更好的？

string intToString(int a){
	string s = "";
	stack stack;
	while (a != 0){
		stack.push('0' + a%10);
		a /= 10;
	}
	while (!stack.empty()){
		s += stack.top();
		stack.pop();
	}
	return s==""? "0":s;
}

//a是否字符串大于等于b
bool compareGreater(int a, int b){
	string sa = intToString(a), sb = intToString(b);
	string s1 = sa + sb;
	string s2 = sb + sa;
	return s1 > s2 ? true : false;
}


class Solution {
public:
	string largestNumber(vector &num) {
		std::sort(num.begin(), num.end(), compareGreater);
		int len = num.size();
		if(len==0 || num[0]==0){
		    return "0";
		}
		string result = "";
		for (int i = 0; i
二次刷题2015-10-14
class Solution {
public:
    string largestNumber(vector& nums) {
        int len = nums.size();
        std::sort(nums.begin(), nums.end(), myCompare);
        if(len == 0 || nums[len - 1] == 0){     //最大的数为0
            return "0";
        }
        string result = "";
        for(int i = len - 1; i>=0; i--){
            result += std::to_string(nums[i]);
        }
        return result;
    }
    static bool myCompare(int a, int b){
        string sa = std::to_string(a);
        string sb = std::to_string(b);
        return sa + sb < sb + sa;               //这里比较巧妙
    }
};

 
转载请注明： » [LeetCode] Largest Number

<!--
                    

                    	

                        	

                            	
                            
                        
                        

                        	

                            	
相关博文：
                                

                                	
                                    	
                                        	
                                        
                                        
定制桌面成功案例
                                    
                                    
                                    	
                                        	
                                        
                                        
海量文档查同或聚类问题 -- Locality Sensitive Hash 算法 （转）
                                    
                                    
                                    	
                                        	
                                        
                                        
汉字转拼音c/c++源码，支持gb2312和utf8
                                    
                                    
                                    	
                                        	
                                        
                                        
数据库顶级会议——SIGMOD介绍
                                    
                                
                            
                        
                    
                    -->