鏈接：https://www.nowcoder.com/questionTerminal/d5d1a56491384b2486480730f78f6da2
來(lái)源：耪锵兀客網(wǎng)
給定一個(gè)字符串的數(shù)組strs蔚叨，請(qǐng)找到一種拼接順序帮碰，使得所有的字符串拼接起來(lái)組成的字符串是所有可能性中字典序最小的辆沦，并返回這個(gè)字符串。
輸入描述:
輸入包含多行紫谷，第一行包含一個(gè)整數(shù)n（1≤n≤105）（ 1 \leq n \leq 10^5 ）（1≤n≤105）轿亮，代表字符串?dāng)?shù)組strs的長(zhǎng)度，后面n行姿搜，每行一個(gè)字符串寡润，代表strs[i]（保證所有字符串長(zhǎng)度都小于10）。
輸出描述:
輸出一行舅柜，包含一個(gè)字符串梭纹，代表返回的字典序最小的字符串。
示例1
輸入
2
abc
de
輸出
abcde
示例2
輸入
2
b
ba
輸出
bab
備注:
時(shí)間復(fù)雜度O（nlog2n）O（nlog_2n）O（nlog2?n）致份，額外空間復(fù)雜度O（1）O（1）O（1）变抽。
思路：利用排序算法。
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool cmp(string& a,string& b)
{
? ? return a + b < b + a;
}
int main()
{
? ? int n;
? ? cin >> n;
? ? vector<string> vs;
? ? for(int i = 0;i < n;i++)
? ? {
? ? ? ? string s;
? ? ? ? cin >> s;
? ? ? ? vs.push_back(s);
? ? }
? ? sort(vs.begin(),vs.end(),cmp);
? ? for(int i = 0;i < n;i++)
? ? {
? ? ? ? cout << vs[i];
? ? }
? ? return 0;
}
另一種：手寫排序氮块。
#include<iostream>
#include<string>
#include<vector>
usingnamespacestd;
classPrior{
public:
string findSmallest(vector strs,intn)
{
QuickSort(strs,0,n-1);
string res;
for(inti=0;i
res+=strs[i];
return res;
? ? }
void QuickSort(vector &strs,int low,int high)
{
if(low<high)
{
intres=Partition(strs,low,high);
QuickSort(strs,low,res-1);
QuickSort(strs,res+1,high);
}
}
int Partition(vector &strs,int low,int high)
{
string key=strs[low];
while(low<high)
{
while(low<high&<(key,strs[high]))
high--;
strs[low]=strs[high];
while(low<high&<(strs[low],key))
low++;
strs[high]=strs[low];
}
strs[low]=key;
return low;
}
bool LT(string s1,string s2)
{
string temp1=s1+s2,temp2=s2+s1;
if(temp1<=temp2)
return true;
else
return false;
}
};
int main()
{
stringa("abc"),b("de"),c("cab");
vector<string> arr;
arr.push_back(b);
arr.push_back(a);
arr.push_back(c);
Prior A;
string res=A.findSmallest(arr,3);
cout<<res;
return 0;
}
