LeetCode OJ：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.

这题也是属于那种算法很重要的那种题目，一开始拿到题目我头都大了，想想怎么样才能够正确的分析出来哪个比哪个大种种情况，后来实在想不出来，看了下别人写的，原来可以是暴力

一点，直接对每个组合组成的数字进行比较（当然是两个两个数字之间），然后排个序，直接相加得到的就是最大的数了。代码如下，实现比较容易：

 class Solution {

 public:

     string largestNumber(vector<int>& nums) {

         stringstream ss;

         vector<string> numStr;

         numStr.clear();

         ss.str("");

         int sz = nums.size();

         for(int i = ; i < sz; ++i){

             ss << nums[i];

             numStr.push_back(ss.str());

             ss.str(""); //清空ss

         }

         sort(numStr.begin(), numStr.end(), Compare);

         string ret = "";

         for(int i = ; i < sz; ++i){

             ret += numStr[i];

         }

         if(ret[] == '')

             ret = "";

         return ret;

     }

     static bool Compare(string s1, string s2)

     {

         string res1 = s1 + s2;

         string res2 = s2 + s1;

         return res1 > res2;

     }

 };

java版本的如下所示，由于String的处理比较方便，可以直接的将Int型转换成一个String，Comparator对象使用起来也较为容易，代码如下所示：

 public class Solution {

     public String largestNumber(int[] nums) {

         int sz = nums.length;

         String [] numStr = new String[sz];

         for(int i = ; i < sz; ++i){

             numStr[i] = String.valueOf(nums[i]);

         }

         Arrays.sort(numStr, new Comparator<String>(){ //这里就不用单独的去创造一个函数对象了，直接new一个使用就可以了

             public int compare(String s1, String s2){

                 String tmp1 = s1+s2;

                 String tmp2 = s2+s1;

                 return tmp2.compareTo(tmp1);

             }

         });

         String ret = new String("");

         for(int i = ; i < sz; ++i){

             ret += numStr[i];

         }

         if(ret.charAt() == '')

             ret = "";

         return ret;

     }

 }

巴特西

LeetCode OJ：Largest Number（最大数字）

最新文章

热门文章