Greedy Algorithm to Compute the 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

The Greedy 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 the STL: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”.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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 (The Ultimate Computing & Technology Blog) —