九号球普通 2023年12月24日下午4:29

“`java
//需要想明白可以用排序
public String crackPassword(int[] password) {
if (password == null || password.length == 0) {
return “”;
}
String[] strs = new String[password.length];
for (int i = 0; i < password.length; i++) { strs[i] = String.valueOf(password[i]); } Arrays.sort(strs, (x,y) -> (x + y).compareTo(y+x));
StringBuilder sb = new StringBuilder();
for (int i = 0; i < password.length; i++) { sb.append(strs[i]); } return sb.toString(); }

0 赞同 0 条回复

招舟子普通 2023年9月8日下午2:35

class Solution {
public String minNumber(int[] nums) {
String[] s=new String[nums.length];
for(int i=0;i<nums.length;i++){
s[i] = String.valueOf(nums[i]);
}
quicksort(s,0,s.length-1);
String res = “”;
for(int i=0;i<s.length;i++){
res=res+s[i];
}
return res;
}
void quicksort(String[] nums,int left,int right){

    if(left<right){
        int i = left,j=right;
        String pivot=nums[left];
    while(i<j){
        while(i<j&&(pivot+nums[j]).compareTo(nums[j]+pivot)<=0){
            j--;
        }
        if(i<j){
            nums[i++]=nums[j];
        }
        while(i<j&&(pivot+nums[i]).compareTo(nums[i]+pivot)>=0){
            i++;
        }
        if(i<j){
            nums[j--]=nums[i];
        }
    }
    nums[i] = pivot;
    quicksort(nums,left,i-1);
    quicksort(nums,i+1,right);
    }

}

}
快速排序的思想

0 赞同 0 条回复

jhfuture 普通 2023年9月5日上午11:48

class Solution {
public String minNumber(int[] nums) {
// 想法1.直接使用快排或者冒泡，然后再逐一拼凑即可。
// 先进行一个数组的转换
// 时间复杂度为 O(n^2) ，空间为 O(1)
String [] s= new String[nums.length];

    for(int i=0;i<nums.length;i++){
        s[i]= String.valueOf(nums[i]);
    }
int length=nums.length;
for(int i=length-1;0<i;i--){
    for(int j=0;j<i;j++){
        // 每一次排都把最大的放到右边
        // if(nums[j]>nums[j+1]){
        //     int tmp=nums[j];
        //     nums[j]=nums[j+1];
        //     nums[j+1]=tmp;
        // }
    if((s[j]+s[j+1]).compareTo(s[j+1]+s[j]) >0){
        //如果大于0，则说明 第一个结合比大二个大，需要进行交换
        String tmp=s[j];
        s[j]=s[j+1];
        s[j+1]=tmp; 
    }else{
        // 没有则不需要
    }
    }
}
String result="";

for(int i=0;i<s.length;i++){
    result=result+s[i];
}
return   result;
}

}

0 赞同 0 条回复

屠龙手段普通 2023年7月30日下午11:21

快排，时间复杂度O(nlogn) 空间复杂度O(1)

class Solution:
    def minNumber(self, nums: List[int]) -> str:
        nums = list(map(lambda x: str(x), nums))
        low, hight = 0, len(nums) - 1
        def quick_sort(low, hight):
            if low >= hight: return
            left, right = low, hight
            while left < right:
                while left < right and nums[low] + nums[right] <= nums[right] + nums[low]: right -= 1
                while left < right and nums[low] + nums[left] >= nums[left] + nums[low]: left += 1
                nums[left], nums[right] = nums[right], nums[left]
            nums[low], nums[left] = nums[left], nums[low]
            quick_sort(low, left - 1)
            quick_sort(left + 1, hight)
        quick_sort(low, hight)
        return ''.join(nums)

0 赞同 0 条回复

怀瑾永久会员 2023年7月19日下午3:42

“`C++
bool compare(int a, int b) {
string str1 = to_string(a) + to_string(b);
string str2 = to_string(b) + to_string(a);
return str1 < str2; } string minNumber(vector& nums) {
string result;

// 对数组中的数字进行排序
sort(nums.begin(), nums.end(), compare);

// 拼接排序后的数字
for (int num : nums) {
    result += to_string(num);
}

return result;

}

“`

0 赞同 0 条回复

BOZ 普通 2023年7月18日下午3:12

【思路】快排思想将数字排序，最后转化为字符串拼接起来
【复杂度】时间复杂度为O(nlogn)，空间复杂度O(1)

class Solution {
    // compare a and b, return true if a > b
    bool compare(int a, int b) {
        std::string as = std::to_string(a);
        std::string bs = std::to_string(b);
        auto ab = [&](int i) -> char {
            if (i >= as.length()) return bs[i - as.length()];
            else return as[i];
        };
        auto ba = [&](int i) -> char {
            if (i >= bs.length()) return as[i - bs.length()];
            else return bs[i];
        };
        for (int i = 0; i < as.length() + bs.length(); i++)
            if (ab(i) > ba(i)) return true;
            else if (ab(i) < ba(i)) return false;
        return true;
    }

    void quickSort(vector<int>& nums, int left, int right) {
        if (left >= right) return;
        int l = left, r = right, mid = nums[left];

        // find the position for mid
        while(l < r) {
            while (compare(nums[r], mid) && l < r) r--;
            while (compare(mid, nums[l]) && l < r) l++;
            if (l < r) std::swap(nums[l], nums[r]);
        }

        // divide the left into left and right 2 parts
        if (compare(nums[left], nums[l])) std::swap(nums[left], nums[l]);
        quickSort(nums, left, l - 1);
        quickSort(nums, l + 1, right);
    }

public:
    string minNumber(vector<int>& nums) {
        quickSort(nums, 0, nums.size() - 1);
        string s;
        for (auto &n: nums)
            s += std::to_string(n);
        return s;
    }
};

0 赞同 0 条回复

江畅普通 2023年7月16日下午3:50

// 把数组排成最小的数
// 时间复杂度 O(NlogN)
// 空间复杂度 O(N)
class Solution {
public:
    string minNumber(vector<int>& nums) {
        vector<string> strs;
        string         res;

        for (int num : nums) {
            strs.push_back(to_string(num));
        }

        sort(strs.begin(), strs.end(), [](string& x, string& y) { return x + y < y + x; });

        for (string str : strs) {
            res.append(str);
        }

        return res;
    }
};

0 赞同 0 条回复

WhyNot 普通 2023年7月16日上午11:01

void integerToArray(int i, char* array) {
    if(i == 0) {
        array[0] = '0';
        array[1] = 0;
        return;
    }
    int index = 0;
    while(i > 0) {
        array[index++] = i % 10 + 48;
        i /= 10;
    }
    array[index] = 0;
    for(int j = 0; j < index / 2; ++j) {
        int tmp = array[j];
        array[j] = array[index - j - 1];
        array[index - j - 1] = tmp;
    }
}

int cmp2(const void* _a, const void* _b) {
    int a = *(int *)_a;
    int b = *(int *)_b;
    char strA[16], strB[16], tmpA[32], tmpB[32];
    integerToArray(a, strA);
    integerToArray(b, strB);
    strcpy(tmpA, strA);
    strcpy(tmpB, strB);
    strcat(tmpA, strB);
    strcat(tmpB, strA);
    return strcmp(tmpA, tmpB);
}

// 把让整体数变大变小看成一种固有属性
char* minNumber(int* nums, int numsSize){
    char* res = (char*)malloc(sizeof(char) * 1000000);
    qsort(nums, numsSize, sizeof(nums[0]), cmp2);
    int index = 0;
    for(int i = numsSize - 1; i >= 0; --i) {
        if(nums[i] == 0) {
            res[index++] = '0';
        } else {
            while(nums[i] > 0) {
                res[index++] = nums[i] % 10 + 48;
                nums[i] /= 10;
            }
        }
    }
    for(int i = 0; i < index / 2; ++i) {
        char tmp = res[i];
        res[i] = res[index - i - 1];
        res[index - i - 1] = tmp;
    }
    res[index] = 0;
    return res;
}

时间复杂度O(numsSize)
空间复杂度为O(1)

0 赞同 0 条回复

哈哈哈哈开开心心普通 2023年7月16日上午7:42

class Solution:
    def minNumber(self, nums: List[int]) -> str:
        def quickSort(arr, l, r):
            if l > r:
                return

            i = partition(arr, l, r)
            quickSort(arr, l, i - 1)
            quickSort(arr, i + 1, r)

        def partition(arr, l, r):
            p = arr[l]
            v, w = l, r

            while v < w:
                while v <= w and arr[v] + p <= p + arr[v]:
                    v += 1

                while v <= w and arr[w] + p >= p + arr[w]:
                    w -= 1

                if v >= w:
                    break

                temp = arr[v]
                arr[v] = arr[w]
                arr[w] = temp

            arr[l] = arr[w]
            arr[w] = p
            return w

        nums = [str(num) for num in nums]
        quickSort(nums, 0, len(nums)-1)

        return "".join(nums)

通过pivot放前或者放后比较

0 赞同 0 条回复

花老爷普通 2023年7月15日下午4:27

自定义排序
时间：O(nlogn)
空间：O(n)

class Solution {
    public String minNumber(int[] nums) {
        Integer[] numsNew = Arrays.stream(nums).boxed().toArray(Integer[]::new);
        Arrays.sort(numsNew, new Comparator<Integer>() {
            public int compare(Integer a, Integer b) {
                String sa = a + "";
                String sb = b + "";
                String res = sa.length() >= sb.length() ? isLarger(sa, sb) : isLarger(sb, sa);
                return res.equals(sa) ? 1 : -1;
            }

            private String isLarger(String f, String s) {
                int lf = f.length(), ls = s.length();
                for (int i = 0; i < lf; i++) {
                    int diff =  f.charAt(i) - s.charAt(i % ls);
                    if (diff > 0) {
                        return f;
                    } else if (diff < 0) {
                        return s;
                    }
                }
                return s.charAt(lf % ls) > s.charAt((lf - 1) % ls) ? s : f;
            }
        });
        StringBuffer sb = new StringBuffer();
        for (int num: numsNew) {
            sb.append(num);
        }
        return sb.toString();
    }
}

0 赞同 0 条回复

yxy 普通 2023年7月14日下午8:50

时间复杂度O(nlogn)

class Solution {
    bool less(int x, int y, vector<int>& nums)
    {
        string sx = to_string(x);
        string sy = to_string(y);
        return sx+sy<sy+sx;
    }

    void qs(int l, int r, vector<int>& nums)
    {
        if(l>=r) return;
        int i=l-1,j=r+1;
        int mid=nums[l+r>>1];
        while(i<j)
        {
            do i++;
            while(less(nums[i],mid,nums));
            do j--;
            while(less(mid,nums[j],nums));
            if(i<j)
                swap(nums[i], nums[j]);
        }
        qs(l,j,nums);
        qs(j+1,r,nums);
    }
public:
    string minNumber(vector<int>& nums) {
        qs(0, nums.size()-1, nums);
        string s;
        for(auto x:nums)
            s+=to_string(x);
        return s;
    }
};

0 赞同 0 条回复

Ming 普通 2023年7月14日下午8:40

我的选择是调用接口

if (nums == null || nums.length == 0) {
            return "";
        }

        // 将数组转换为字符串数组
        String[] strNums = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            strNums[i] = String.valueOf(nums[i]);
        }

        // 自定义比较器
        Comparator<String> comparator = new Comparator<String>() {
            @Override
            public int compare(String str1, String str2) {
                String s1 = str1 + str2;
                String s2 = str2 + str1;
                return s1.compareTo(s2);
            }
        };

        // 使用自定义比较器对字符串数组进行排序
        Arrays.sort(strNums, comparator);

        // 拼接排序后的字符串数组
        StringBuilder sb = new StringBuilder();
        for (String str : strNums) {
            sb.append(str);
        }

        return sb.toString();

0 赞同 0 条回复

行动派小彩笔普通 2023年7月13日下午8:44

// 核心思想是排序
// 时间复杂度O(nlogn) 空间复杂度O(n)
class Solution {
public:
    string minNumber(vector<int>& nums) {
        vector<string> strs;
        for(int i =0;i<nums.size();++i)
        {
            strs.push_back(to_string(nums[i]));
        }
        quickSort(strs,0,strs.size()-1);
        string res;
        for(int i = 0;i<strs.size();++i)
        {
            res+=strs[i];
        }
        return res;
    }
    void quickSort(vector<string>& arr ,int left,int right)
    {
        if(left>right) return;  
        int i = qartition(arr,left,right);
        quickSort(arr,left,i-1);
        quickSort(arr,i+1,right);
    }
    int qartition(vector<string>&arr,int left,int right)
    {
        string pivot = arr[left];
        int i = left;
        int j = right;
        while(i<j)
        {
            while(i<=j && (arr[i]+pivot)<=(pivot+arr[i])) ++i;

            while(i<=j && (arr[j]+pivot)>=(pivot+arr[j])) --j;

            if(i>=j) break;

            swap(arr[i],arr[j]);
        }
        arr[left] = arr[j];
        arr[j] = pivot;
        return j;
    }
};

0 赞同 0 条回复

Vow the vow。普通 2023年7月13日上午11:27

快排。

public String minNumber(int[] nums) {
        String[] strs = new String[nums.length];
        for(int i = 0; i < nums.length; i++){
            strs[i] = String.valueOf(nums[i]);
        }
        quickSort(strs, 0, nums.length-1);
        StringBuilder sb = new StringBuilder();
        for(String s : strs){
            sb.append(s);
        }
        return sb.toString();
    }

    public void quickSort(String[] strs, int l, int r){
        if(l >= r) return;
        int partition = partition(strs, l, r);
        quickSort(strs,l,partition-1);
        quickSort(strs,partition+1,r);
    }

    public int partition(String[] strs, int l, int r){
        int i = l, j = r;
        String temp  = strs[i];
        while(i < j){
            while(i < j && (strs[j] + strs[l]).compareTo(strs[l] + strs[j]) >= 0) j--;
            while(i < j && (strs[i] + strs[l]).compareTo(strs[l] + strs[i]) <= 0) i++;
            temp = strs[i];
            strs[i] = strs[j];
            strs[j] = temp;
        }
        strs[i] = strs[l];
        strs[l] = temp;
        return i;
    }

0 赞同 0 条回复

局外人普通 2023年7月12日下午11:16

思路：按照字符串拼接排序
时间复杂度O(n) 空间复杂度O(1)

class Solution {
    public String minNumber(int[] nums) {
        int n = nums.length;
        String[] list = new String[n];
        for(int i=0; i<n; i++){
            list[i] = Integer.toString(nums[i]);
        }
        Arrays.sort(list, (s1, s2)->{
            return (s1+s2).compareTo(s2+s1);
        });

        return String.join("", list);
    }
}

0 赞同 0 条回复

张君雅小妹妹普通 2023年7月12日下午10:41

时间复杂度：O(nlogn)
空间复杂度：O(n)

class Solution {
    public String minNumber(int[] nums) {
        if(nums == null || nums.length == 0) return null;

        String[] numStr = new String[nums.length];
        for(int i = 0; i < nums.length; i++){
            numStr[i] = String.valueOf(nums[i]);
        }
        quickSort(numStr, 0, numStr.length - 1);
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < numStr.length; i++){
            sb.append(numStr[i]);
        }        
        return sb.toString();
    }

    public void quickSort(String[] nums, int left, int right){
        if(left > right) return;
        int p = partition(nums, left, right);
        quickSort(nums, left, p - 1); // 不再比较p
        quickSort(nums, p + 1, right);
    }


    public int partition(String[] nums, int left, int right){
        String pivot = nums[left];
        int i = left, j = right;
        while(i < j){
            while(i <= j && (pivot + nums[i]).compareTo(nums[i] + pivot) >= 0){
                i++;
            }

            while(i <= j && (pivot + nums[j]).compareTo(nums[j] + pivot) <= 0){
                j--;
            }

            if(i < j){
                swap(nums, i, j);
            }           
        }

        nums[left] = nums[j];
        nums[j] = pivot;
        return j;
    }

    public void swap(String[] nums, int i, int j){
        String tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

0 赞同 0 条回复

小吕普通 2023年7月12日下午9:19

c++实现
string minNumber(vector& nums) {
sort(nums.begin(),nums.end(),[](int n1,int n2){
string s1= to_string(n1);
string s2 = to_string(n2);
return (s1+s2)<(s2+s1);
});
string ret;
for(auto num:nums)
{
ret+=to_string(num);
}
return ret;
}

0 赞同 0 条回复

mpweixin用户永久会员 2023年7月12日下午5:38

public String minNumber(int[] nums) {

        //转为字符创数组
        String[] strs = new String[nums.length];

        for (int i = 0; i < nums.length; i++) {
            strs[i] = String.valueOf(nums[i]);
        }

        //快排
        quickSort(strs, 0, strs.length - 1);

        //拼接
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < strs.length; i++) {
            sb.append(strs[i]);
        }
        return sb.toString();
    }

    private void quickSort(String[] arr, int left, int right) {
        if (left > right) {
            return;
        }
        int i = partition(arr, left, right);
        quickSort(arr, left, i - 1);
        quickSort(arr, i + 1, right);

    }

    int partition(String[] arr, int left, int right){
       String pivot = arr[left]; // 中间值
        int i = left;
        int j = right;

        while (i < j) {

            while (i <= j && (arr[i] + pivot).compareTo(pivot + arr[i]) <= 0) {
                //满足，判断下一个位置
                i++;
            }

            while (i <= j && (arr[j] + pivot).compareTo(pivot + arr[j]) >= 0) {
                j--;
            }
            if(i >= j){
                break;
            }
            //不满足，交换
            String temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }

        arr[left] = arr[j];
        arr[j] = pivot;

        return j;

    }

0 赞同 0 条回复

张开怀普通 2023年7月12日下午4:48

class Solution{
public:
       string minNumber(vector<int>& nums){
              vector<string> strs;
              for(int i =0;i< nums.size(); i++){
                     strs.push_back(to_string(nums[i]));
              }
              quickSort(strs, 0, strs.size()-1);
              string res;
              for(int i=0;i<strs.size();i++){
                     res += strs[i];
              }
              return res;
       }
private:
       void quickSort(vector<string>& arr,int left, int right){
              if(left > right){
                     return;
              }
              int i = partition(arr, left, right);
              quickSort(arr, left, i-1);
              quickSort(arr, i+1, right);
       }

       int partition(vector<string>& arr, int left, int right){
              string pivot = arr[left];
              int i = left;
              int j = right;
              while(i<j){
                     while(i<=j && (arr[i] + pivot) <= (pivot + arr[i])){
                            i++;
                     }
                     while(i<=j && (arr[j] + pivot) <= (pivot + arr[j])){
                            j--;
                     }
                     if(i>=j){
                           break;
                     }
                     string temp = arr[j];
                     arr[i] = arr[j];
                     arr[j] = temp;
              }
              arr[left] = arr[j];
              arr[j] = pivot;
              return j;
       }
};

时间复杂度：O(nlogn)
空间复杂度：O(n)

0 赞同 0 条回复

Dsjh 普通 2023年7月12日下午3:33

MY

排序规则
x+y < y+x, x<y

class Solution {
public:
    string minNumber(vector<int>& nums) {
        vector<string> v;
        for(int& i:nums){
            v.push_back(to_string(i));
        }
        sort(v.begin(),v.end(),[](string& s1,string& s2)->bool{
            string t1 = s1+s2;
            string t2 = s2+s1;
            return t1<t2;
        });
        string ans;
        for(string& s:v){
            ans += s;
        }
        return ans;
    }
};

0 赞同 0 条回复

Yodl. 普通 2023年7月12日下午3:10

//可证明：若x+y < y+x,则x < y。
class Solution {
public:
    string minNumber(vector& nums) {
        vector strs;
        for (int i = 0; i < nums.size(); i++) {
            strs.push_back(to_string(nums[i]));
        }

        quickSort(strs, 0, strs.size() - 1);

        string res;
        for (int i = 0; i < strs.size(); i++) {
            res += strs[i];
        }
        return res;
    }

private:
    // 快速排序模版（和普通快速排序模版一样的，除了比较那里不一样）
    void quickSort(vector& arr, int left, int right) {
        if (left > right) {
            return;
        }
        int i = partition(arr, left, right);
        quickSort(arr, left, i - 1);
        quickSort(arr, i + 1, right);
    }

    int partition(vector& arr, int left, int right) {
        string pivot = arr[left];
        int i = left;
        int j = right;

        while (i < j) {
            while (i <= j && (arr[i] + pivot) <= (pivot + arr[i])) {
                i++;
            }

            while (i <= j && (arr[j] + pivot) >= (pivot + arr[j])) {
                j--;
            }

            if (i >= j) {
                break;
            }

            string temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }

        arr[left] = arr[j];
        arr[j] = pivot;
        return j;
    }
};

0 赞同 0 条回复

【排序算法运用】剑指 Offer 45. 把数组排成最小的数

共以下 21 个回答

MY

# 回答此问题取消回复

【排序算法运用】剑指 Offer 45. 把数组排成最小的数

共以下 21 个回答

MY

# 回答此问题 取消回复

# 回答此问题取消回复