神刀安全网

C++ Coding Exercise – Largest Number

Arrange a list of non negative integers such that they form the largest number. For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330. The result may be very large, so you need to return a string instead of an integer.

Greedy Algorithm

TheGreedy Algorithm (GA) always choose the best at the current iteration. Given two numbers a and b, we pick the larger number if the string concatenation of a+b is bigger than b+a, for example, 34, 5 we pick 5 because 534 is bigger than 345. 90 and 180 we pick 90 because 90180 is bigger than 18090.

So, we know to to compare two numbers, in this customize way. We can create a sort function comparator (has to be static in C++) and use theSTL:sort function to sort the numbers in the non-descending order. Adding these numbers (in string format) one by one.

If all numbers are zero, we need to return “0”.

class Solution { public:     static bool sortfunc(int a, int b) {         return to_string(a) + to_string(b) > to_string(b) + to_string(a);     }          string largestNumber(vector<int>& nums) {         sort(nums.begin(), nums.end(), sortfunc);         string r = "";         for (auto num: nums) {             r += to_string(num);         }         return r[0] == '0' ? "0" : r;     } };
class Solution { public:     static bool sortfunc(int a, int b) {         return to_string(a) + to_string(b) > to_string(b) + to_string(a);     }          string largestNumber(vector<int>& nums) {         sort(nums.begin(), nums.end(), sortfunc);         string r = "";         for (auto num: nums) {             r += to_string(num);         }         return r[0] == '0' ? "0" : r;     } };

O(nlogn) complexity, O(1) space complexity.

–EOF–

GD Star Rating

loading…

265 words

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » C++ Coding Exercise – Largest Number

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址