Given a list of non-negative integers nums, arrange them such that they form the largest number and return it.
Since the result may be very large, so you need to return a string instead of an integer.
OR
As the last question of a successful interview, your boss gives you a few pieces of paper with numbers on it and asks you to compose a largest number from these numbers. The resulting number is going to be your salary, so you are very much interested in maximizing this number. How can you do this?
This problem will be solved by greedy. We should put higher number before lower one. For eg. 9 before 5 OR 9 before 34, as that will give us 95 and 934 respectively. Also, when we have same digit numbers like 35 and 34, then 35 should come before 34.
This problem can be solve by simply sorting strings, not sorting integer. Sorting integers will make 34 before 9, which will break our case.
Define a comparator to compare strings by concat() right-to-left or left-to-right.
classSolution {
public: std::string largestNumber(std::vector<int>& nums) {
std::vector<std::string> arr;
arr.reserve(nums.size());
for (int x : nums) arr.push_back(std::to_string(x));
std::sort(arr.begin(), arr.end(), [](const std::string& a, const std::string& b) {
// Put a before b if a+b > b+a
return a + b > b + a;
});
if (arr.size() && arr[0] =="0") return"0"; // all zeros
std::string result;
result.reserve(arr.size() *10); // rough pre-allocation
for (auto& s : arr) result += s;
return result;
}
};
classSolution:
deflargestNumber(self, nums: List[int]) -> str:
arr = [str(x) for x in nums]
# Python's sort can't take a comparator directly (since 3.x), so we use functools.cmp_to_keyfrom functools import cmp_to_key
defcmp(a: str, b: str) -> int:
if a + b > b + a:
return-1# a should come firstif a + b < b + a:
return1return0 arr.sort(key=cmp_to_key(cmp))
if arr[0] =='0': # all zerosreturn'0'return''.join(arr)