179. Largest Number

  • 21.8%

https://leetcode.com/problems/largest-number/?tab=Description

Given a list of non negative integers, arrange them such that they form the largest number.

1
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.


方法一:

剑指offer 33

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
string largestNumber(vector<int>& nums) {
sort(nums.begin(), nums.end(),
[](int a, int b){return to_string(a)+to_string(b)>to_string(b)+to_string(a);});
string res;
for(int i=0; i<nums.size(); i++)z
res += to_string(nums[i]);
// 学习erase的用法 erase(pos, len)
while(res.size()>1 && res[0]=='0')
res.erase(0, 1);
return res;
}
};

转换成string,然后比较,相加,考虑第一个值为0的情况

https://discuss.leetcode.com/topic/7286/a-simple-c-solution

A simple C++ solution

先变成字符串排序,然后累加,再进行删除前面的0

简单直接

此处学习to_string 的用法,还有erase的用法。

string此处用的begin(arr),不同于vector的arr.begin()

后面的比较也是引用

erase(0, 1) erase(start, end), 其中删除关系[start, end)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
string largestNumber(vector<int> &num) {
vector<string> arr;
for(auto i:num)
arr.push_back(to_string(i));
sort(begin(arr), end(arr), [](string &s1, string &s2){ return s1+s2>s2+s1; });
string res;
for(auto s:arr)
res+=s;
while(res[0]=='0' && res.length()>1)
res.erase(0,1);
return res;
}
};

erase 的用法

iterator erase (iterator position);

iterator erase (iterator first, iterator last);

position

Iterator pointing to a single element to be removed from the vector.

Member types iterator and const_iterator are random access iterator types that point to elements.

first, last

Iterators specifying a range within the vector] to be removed: [first,last). i.e., the range includes all the elements between first and last, including the element pointed by first but not the one pointed by last.

Member types iterator and const_iterator are random access iterator types that point to elements.

剑指offer 33

把数组排成最小的数

输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。

方法一:

题目为正数,如果有0,则加上代码中注释的代码

整数转string的函数to_string(a)

string可以相加 a+b

如果有必要,检查边界是否有0的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
string PrintMinNumber(vector<int> numbers) {
string res = "";
sort(numbers.begin(), numbers.end(), [](int a, int b)
{return to_string(a)+to_string(b)<to_string(b)+to_string(a);});
for(auto num:numbers)
res += to_string(num);
//while(res[0]=='0' && res.length()>1)
// res.erase(0,1);
return res;
}
};

https://discuss.leetcode.com/topic/10920/share-a-short-code-in-c

Share a short code in c++

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
string largestNumber(vector<int> &num) {
sort(num.begin(), num.end(), [](int a, int b){
return to_string(a)+to_string(b) > to_string(b)+to_string(a);
});
string ans;
for(int i=0; i<num.size(); i++){
ans += to_string(num[i]);
}
return ans[0]=='0' ? "0" : ans;
}
};

https://discuss.leetcode.com/topic/12293/simple-10-line-c-solution

Simple 10-line C++ Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
string largestNumber(vector<int>& nums) {
string ret;
sort(nums.begin(),nums.end(),
[](const int &m,const int&n){
return to_string(m)+to_string(n)>to_string(n)+to_string(m);});
for(int i=0;i<nums.size();++i){
ret+=to_string(nums[i]);
}
if(ret[0]=='0') //for the case nums are all zeros
return "0";
return ret;
}
};

https://discuss.leetcode.com/topic/7722/python-simple-solution-in-4-lines

Python simple solution in 4 lines

It’s all about comparison . We define a func that compares two strings a ,b. we consider a bigger than b if a+b > b+a . then we sort the numbers and concatenate them .

1
2
3
4
5
6
7
8
class Solution:
# @param num, a list of integers
# @return a string
def largestNumber(self, num):
comp=lambda a,b:1 if a+b>b+a else -1 if a+b<b+a else 0
num=map(str,num)
num.sort(cmp=comp,reverse=True)
return str(int("".join(num)))

UPDATE

More explanation

1-we define a function that compares two string (a,b) . we consider a bigger than b if a+b>b+a
for example : (a=”2”,b=”11”) a is bigger than b because “211” >”112”

2-convert all elements of the list from int to string

3-sort the list descendingly using the comparing function we defined
for example sorting this list [“2”,”11”,”13”] using the function defined in step 1 would produce [“2”,”13”,”11”]

4-we concatatenate the list “21311”


https://discuss.leetcode.com/topic/7235/my-3-lines-code-in-java-and-python

My 3-lines code in Java and Python

The logic is pretty straightforward. Just compare number by convert it to string.

Thanks for Java 8, it makes code beautiful.

Java:

1
2
3
4
5
6
7
public class Solution {
public String largestNumber(int[] num) {
String[] array = Arrays.stream(num).mapToObj(String::valueOf).toArray(String[]::new);
Arrays.sort(array, (String s1, String s2) -> (s2 + s1).compareTo(s1 + s2));
return Arrays.stream(array).reduce((x, y) -> x.equals("0") ? y : x + y).get();
}
}

Python:

class Solution:

1
2
3
4
5
6
# @param num, a list of integers
# @return a string
def largestNumber(self, num):
num = [str(x) for x in num]
num.sort(cmp=lambda x, y: cmp(y+x, x+y))
return ''.join(num).lstrip('0') or '0'

https://discuss.leetcode.com/topic/32442/share-my-fast-java-solution-beat-98-64

Share my fast JAVA solution, beat 98.64%!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
public String largestNumber(int[] nums) {
if (nums == null || nums.length == 0) return "";
String[] strs = new String[nums.length];
for (int i = 0; i < nums.length; i++) {
strs[i] = nums[i]+"";
}
Arrays.sort(strs, new Comparator<String>() {
@Override
public int compare(String i, String j) {
String s1 = i+j;
String s2 = j+i;
return s1.compareTo(s2);
}
});
if (strs[strs.length-1].charAt(0) == '0') return "0";
String res = new String();
for (int i = 0; i < strs.length; i++) {
res = strs[i]+res;
}
return res;
}
}

https://discuss.leetcode.com/topic/8018/my-java-solution-to-share

My Java Solution to share

The idea here is basically implement a String comparator to decide which String should come first during concatenation. Because when you have 2 numbers (let’s convert them into String), you’ll face only 2 cases:

1
2
3
4
5
6
7
For example:

String s1 = "9";
String s2 = "31";

String case1 = s1 + s2; // 931
String case2 = s2 + s1; // 319

Apparently, case1 is greater than case2 in terms of value.
So, we should always put s1 in front of s2.

I have received many good suggestions from you in this discussion. Below is the modified version of codes based on your suggestions:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class Solution {
public String largestNumber(int[] num) {
if(num == null || num.length == 0)
return "";

// Convert int array to String array, so we can sort later on
String[] s_num = new String[num.length];
for(int i = 0; i < num.length; i++)
s_num[i] = String.valueOf(num[i]);

// Comparator to decide which string should come first in concatenation
Comparator<String> comp = new Comparator<String>(){
@Override
public int compare(String str1, String str2){
String s1 = str1 + str2;
String s2 = str2 + str1;
return s2.compareTo(s1); // reverse order here, so we can do append() later
}
};

Arrays.sort(s_num, comp);
// An extreme edge case by lc, say you have only a bunch of 0 in your int array
if(s_num[0].charAt(0) == '0')
return "0";

StringBuilder sb = new StringBuilder();
for(String s: s_num)
sb.append(s);

return sb.toString();

}
}

In terms of Time and Space Complexity:
Let’s assume:
the length of input array is n,
average length of Strings in s_num is k,
Then, compare 2 strings will take O(k).
Sorting will take O(nlgn)
Appending to StringBuilder takes O(n).
So total will be O(nklgnk) + O(n) = O(nklgnk).

Space is pretty straight forward: O(n).

谢谢你,可爱的朋友。