算法1
(暴力枚举) $O(n^2)$
这题其实是定义一种比较方法,然后排序,排序的速度决定了时间复杂度
这里用的冒泡排序,可以尝试其他排序算法
C++ 代码
class Solution {
public:
string convert(int x){
string s ="";
while(x>0){
int m = x%10;
x/=10;
s.push_back(m+'0');
}
reverse(s.begin(),s.end());
return s;
}
string compare(string s1,string s2){
string a = s1+s2; //mn
string b = s2+s1; //nm
for (int i=0;i<a.size();i++){
if(a[i]-'0' > b[i]-'0'){
return s2;
}
else if(a[i]-0<b[i]-0){
return s1;
}
else{
continue;
}
}
return s1;
}
string printMinNumber(vector<int>& nums) {
vector<string> sw;
//vector<vector<int>> sw;
for(auto x:nums){
string s = convert(x);
sw.push_back(s);
}
string res = "";
string s2,s1,p;
for(int i=0;i<sw.size();i++){
for (int j = 0;j<sw.size()-1-i;j++){
s2 = sw[j];
s1 = sw[j+1];
p = compare(s1,s2);
if (p == s1){
sw[j+1] = sw[j];
sw[j] = p;
}
}
}
for(int i=0;i<sw.size();i++){
res+=sw[i];
}
return res;
}
};