class Solution:
def crackPassword(self, password: List[int]) -> str:
def order(a,b):
if a + b < b + a:
return -1
elif a + b > b + a:
return 1
else:
return 0
nums = [str(i) for i in password]
nums.sort(key = functools.cmp_to_key(order))
return “”.join(nums)
时间 nlog n 空间 n
shuaidi
共以下 14 个回答
public String crackPassword(int[] password) {=0)
String[] strs=new String[password.length];
for(int i=0;i<password.length;i++){
strs[i] = String.valueOf(password[i]);
}
quickSort(strs,0,strs.length-1);
StringBuilder res= new StringBuilder();
for(String s:strs)
res.append(s);
return res.toString();
}
public void quickSort(String[] strs,int l,int r){
if(l<r){
int mid=getMid(strs,l,r);
quickSort(strs,l,mid-1);
quickSort(strs,mid+1,r);
}
}
public int getMid(String[] strs,int l,int r){
String temp=strs[l];
while(l<r){
while(l
r–;
strs[l]=strs[r];
while (l < r && (strs[l] + temp).compareTo(temp + strs[l]) <= 0)
l++;
//把比基准大的数移到高端
strs[r] = strs[l];
}
strs[l] = temp;
return l;
}
}
思路：将数字专为string 用compartTo来比较 +快排实现
java
class Solution {
public String crackPassword(int[] nums) {
String[] strs = new String[nums.length];
}
提交
class Solution {& password) { strs; & strs, int l, int r) {
public:
string crackPassword(vector
vector
for(int i = 0; i < password.size(); i++)
strs.push_back(to_string(password[i]));
quickSort(strs, 0, strs.size() – 1);
string res;
for(string s : strs)
res.append(s);
return res;
}
private:
void quickSort(vector
if(l >= r) return;
int i = l, j = r;
while(i < j) {
while(strs[j] + strs[l] >= strs[l] + strs[j] && i < j) j–;
while(strs[i] + strs[l] <= strs[l] + strs[i] && i < j) i++;
swap(strs[i], strs[j]);
}
swap(strs[i], strs[l]);
quickSort(strs, l, i – 1);
quickSort(strs, i + 1, r);
}
};
打卡
时间nlogn，空间 On
时间复杂度：O(nlogn) 空间复杂度：O(n)
思路：快排
“`c++& password) { strs; &pstr, int left, int right) {
class Solution {
public:
string crackPassword(vector
vector
for (int &pw: password) {
strs.push_back(to_string(pw));
}
quickSort(strs, 0, strs.size()-1);
string ans;
for (string &s: strs) {
cout << s << " "; ans.append(s); } return ans; } void quickSort(vector
if (left >= right) return;
int i = left, j = right;
while (i < j) { while (i < j && pstr[j] + pstr[left] > pstr[left] + pstr[j]) –j;
while (i < j && pstr[i] + pstr[left] <= pstr[left] + pstr[i]) ++i; swap(pstr[i], pstr[j]); } swap(pstr[i], pstr[left]); quickSort(pstr, left, i-1); quickSort(pstr, i+1, right); } }; ```
时间复杂度：O(nlogn)
空间复杂度：O(n)
class Solution {& password) { strs;
public:
string crackPassword(vector
//整型转成字符串型数组
vector
for(int i =0;i<password.size();i++){
strs.push_back(to_string(password[i]));
}
//排序
sort(strs.begin(),strs.end(),[](string& x, string& y){ return x + y < y + x; });
//合并字符串
string c;
for(string s: strs){
c.append(s);
}
return c;
}
};
class Solution:
def crackPassword(self, password: List[int]) -> str:
def order(a,b):
if a + b < b + a:
return -1
elif a + b > b + a:
return 1
else:
return 0
nums = [str(i) for i in password]
nums.sort(key = functools.cmp_to_key(order))
return “”.join(nums)
时间 nlog n 空间 n
时间复杂度：O(nlogn)
额外空间复杂度：O(n)
class Solution {& password) { strs; & strs, int l, int r) {
public:
string crackPassword(vector
vector
for(int i = 0; i < password.size(); i++)
strs.push_back(to_string(password[i]));
quickSort(strs, 0, strs.size() – 1);
string res;
for(string s : strs)
res.append(s);
return res;
}
private:
void quickSort(vector
if(l >= r) return;
int i = l, j = r;
while(i < j) {
while(strs[j] + strs[l] >= strs[l] + strs[j] && i < j) j–;
while(strs[i] + strs[l] <= strs[l] + strs[i] && i < j) i++;
swap(strs[i], strs[j]);
}
swap(strs[i], strs[l]);
quickSort(strs, l, i – 1);
quickSort(strs, i + 1, r);
}
};
时间复杂度O（nlogn）空间复杂度O（logn）
class Solution {
public String crackPassword(int[] password) {
StringBuffer ans = new StringBuffer(“”);
String[] s = new String[password.length];
for(int i = 0; i < password.length; i++){
s[i] = “” + password[i];
}
quickSort(s,0,s.length-1);
for(int i = 0; i < s.length; i++)
ans.append(s[i]);
return ans.toString();
}
private void quickSort(String[] password,int l,int r){
if(l >= r)
return;
int i = l;
int j = r;
String key = password[i];
while(i < j){
while((password[j] + key).compareTo(key + password[j]) >= 0 && i < j){
j–;
}
password[i] = password[j];
while((password[i] + key).compareTo(key + password[i]) <= 0 && i < j){
i++;
}
password[j] = password[i];
}
password[i] = key;
quickSort(password,l,i-1);
quickSort(password,j+1,r);
}
}
//使用快排对string数组排序
时间复杂度Onlogn
空间复杂度On
打卡