当前位置：
  1. 首页
  2. 剑指offer刷题第四期
  3. 问题详情

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

本问题对应课程链接：剑指offer刷题第四期

要求：

1、请打卡你的解题代码，如果能简单说一下思路则简单说一下思路。
2、给出你代码所用的时间复杂度和空间复杂度

shuaidi
101 15

共以下 15 个回答

  • hi 普通 2023年10月26日 下午3:09
    1. 该题的主要是定义一个新的比较规则：ab < ba => a < b，根据新的比较规则排好序取出答案
    2. 注意：ab 结合在一起是字符间的结合，需要把数字转为字符
    class Solution {
public: 
    static bool cmp(int a, int b){
        string as = to_string(a), bs = to_string(b);
        return as + bs < bs + as;
    }

    string crackPassword(vector<int>& password) {
        sort(password.begin(), password.end(), cmp);
        //但此时还是以数组元素的形式存在数组中，需要把它们取出来变成字符串
        string res;
        for(auto& x : password) res += to_string(x);

        return res;
    }
};
    0 赞同 0 条回复
  • 桎梏 普通 2023年9月11日 上午10:36 
    // 快排
class Solution {
    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]);
        }
        Arrays.sort(strs, (x, y) -> (x+y).compareTo(y+x));
        StringBuilder res = new StringBuilder();
        for(String str : strs) {
            res.append(str);
        }
        return res.toString();
    }

}
    0 赞同 0 条回复
  • June 普通 2023年9月10日 下午7:50 
    class Solution {
    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 ans = new StringBuilder();
        for(String s : strs)
            ans.append(s);
        return ans.toString();
    }

    void quickSort(String[] strs, int L,int R)
    {
        if(L >= R)
            return;
        int i=L , j=R;
        String tmp = strs[i];
        while(i < j)
        {
            String split = strs[L];
            // 拼接字符串 strs[i]+strs[j] > strs[j]+strs[i] 则 排序后 strs[i]在strs[i]右边
            while((strs[j]+split).compareTo(split+strs[j]) >= 0 && i < j) 
                j--;
            while((strs[i]+split).compareTo(split+strs[i]) <= 0 && i < j)
                i++;
            tmp = strs[i];
            strs[i] = strs[j];
            strs[j] = tmp;
        }
        strs[i] = strs[L];
        strs[L] = tmp;
        quickSort(strs,L,i-1);
        quickSort(strs,i+1,R);
    }
}
    0 赞同 0 条回复
  •  普通 2023年8月16日 下午10:12

    c++ 代码
    class Solution {
    public:
    string minNumber(vector& nums)
    {
    vector str;
    string res;
    for(int i=0;i<nums.size();i++)
    str.push_back(to_string(nums[i]));
    sort(str.begin(),str.end(),{return x+y<y+x;});
    for(int i=0;i<str.size();i++)
    res.append(str[i]);
    return res;
    }
    };

    0 赞同 0 条回复
  • 北辰 普通 2023年8月8日 下午12:09 
    class Solution {
    public String minNumber(int[] nums) {
        String[] strs = new String[nums.length];
        for(int i = 0;i=r) return;
        int i=l,j=r;
        String tmp = strs[i];
        while(i=0&&i

    时间：O（nlogn)
    空间：O（n)

    0 赞同 0 条回复
  • CKX 普通 2023年8月8日 上午12:44 
    func minNumber(nums []int) string {
    str := toString(nums)
    quickSort(str, 0, len(str)-1)
    var res string
    for _, char := range str {
        res += char
    }
    return res
}

func quickSort(str []string, i, j int) {
    if i < j {
        pivot := partition(str, i, j)
        quickSort(str, i, pivot-1)
        quickSort(str, pivot+1, j)
    }
}

func partition(str []string, i, j int) int {
    pivot := str[i]
    for i < j {
        for i < j && str[j]+pivot >= pivot+str[j] {
            j--
        }
        str[i] = str[j]
        for i < j && str[i]+pivot <= pivot+str[i] {
            i++
        }
        str[j] = str[i]
    }
    str[i] = pivot
    return i
}

func toString(nums []int) []string {
    res := make([]string, 0)
    for _, num := range nums {
        res = append(res, strconv.Itoa(num))
    }
    return res
}
    • 时间O(nlogn)
    • 空间O(n)
    0 赞同 0 条回复
  • 艺 普通 2023年8月5日 下午5:35

    “`c++
    //冒泡
    class Solution {
    public:
    string minNumber(vector& nums) {
    int i,j;
    for(i = 0;i < nums.size() - 1;++i){ for(j = 0;j < nums.size() - 1 - i;++j){ if(to_string(nums[j]) + to_string(nums[j+1]) > to_string(nums[j+1]) + to_string(nums[j])){
    swap(nums[j],nums[j+1]);
    }
    }
    }
    string res;
    for(auto it:nums){
    res += to_string(it);
    }
    return res;
    }
    };

    0 赞同 0 条回复
  • #00456B 普通 2023年8月5日 上午12:10

    最终就是一个排序的问题，这里用快排

    class Solution {
public:
    string minNumber(vector<int>& nums) {
        vector<string> str;
        for(auto x:nums){
            str.push_back(to_string(x));
        }
        quickSort(str, 0, nums.size()-1);
        string ans = "";
        for(auto x:str){
            ans += x;
        }
        return ans;
    }
    void quickSort(vector<string>& str, int left, int right){
        if(left > right){
            return ;
        }
        int i = partition(str, left, right);
        quickSort(str, left, i - 1);
        quickSort(str, i + 1, right);
    }
    int partition(vector<string>& str, int left, int right){
        string pivot = str[left];
        int i = left;
        int j = right;
        while(i <= j){
            while(i <= j && str[i] + pivot <= pivot + str[i]){
                i++;
            }
            while(i <= j && str[j] + pivot >= pivot + str[j]){
                j--;
            }
            if(i >= j){
                break;
            }
            swap(str[i],str[j]);
        }
        swap(str[j], str[left]);
        return j;
    }
};
    0 赞同 0 条回复
  • Marshan 普通 2023年8月3日 下午3:28

    还是排序问题,判断哪个数字排前面,哪个排后面,以前是通过比大小决定,这边是通过// to_string(x) + to_string(y) < to_string(y) + to_string(x),则x < y;决定

    class Solution {
public:
    string minNumber(vector<int>& nums) {
        // to_string(x) + to_string(y) < to_string(y) + to_string(x),则x < y;
        for(int i = 0;i < nums.size() - 1;++i){
            for(int j = 0;j < nums.size() - 1 - i;++j){
                if(to_string(nums[j]) + to_string(nums[j+1]) > to_string(nums[j+1]) + to_string(nums[j])){
                    swap(nums[j],nums[j+1]);
                }
            }
        }
        string res = "";
        for(auto it:nums){
            res += to_string(it);
        }
        return res;
    }
};

    class Solution {
public:
    string minNumber(vector<int>& nums) {
        // to_string(x) + to_string(y) < to_string(y) + to_string(x),则x < y;
        vector<string> strs;
        for(auto it:nums){
            strs.push_back(to_string(it));
        }

        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 = 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;
            }

            swap(arr[i],arr[j]);
        }
        arr[left] = arr[j];
        arr[j] = pivot;
        return j;
    }
};
    0 赞同 0 条回复
  • Mby 普通 2023年8月2日 下午10:28 
    class Solution {
    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();
    }
    //时间nlogn， 空间On
    //快速排序模板
    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;
        //时间复杂度：O(nlogn)
        //空间复杂度：O(n)
    }
}
    0 赞同 0 条回复
  • 人生何处不青山 普通 2023年8月1日 下午11:32

    JS一行搞定

    function minNumber(nums: number[]): string {
    return nums.sort((a, b) => { return +`${a}${b}` - +`${b}${a}` }).join('')
};
    0 赞同 0 条回复
  • AD钙奶 普通 2023年8月1日 上午10:41

    快排

    class Solution {
    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]);
        }

        partition(strs,0,nums.length - 1);
        StringBuilder sb = new StringBuilder();
        for(String str : strs) {
            sb.append(str);
        }
        return sb.toString();
    }

    void partition(String[] strs, int left, int right) {
        if(left >= right) return ;
        int i = left, j = right;

        String pivot = strs[i];

        while(i < j) {
            while(i < j && (strs[j] + strs[left]).compareTo(strs[left] + strs[j]) >= 0) j --;
            while(i < j && (strs[i] + strs[left]).compareTo(strs[left] + strs[i]) <= 0) i ++;

            if(i < j) {
                String temp = strs[i];
                strs[i] = strs[j];
                strs[j] = temp;
            }
        }
        strs[left] = strs[i];
        strs[i] = pivot;

        partition(strs, left, i - 1);
        partition(strs, i + 1, right);
    }
}
    0 赞同 0 条回复
  • 长河呼叫黄江 普通 2023年7月31日 下午11:49

    7.31
    Day22：下面是代码

    class Solution {
    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]);
        }
        Arrays.sort(strs, (x, y) -> (x + y).compareTo(y + x));
        StringBuilder res = new StringBuilder();
        for(String s : strs){
            res.append(s);
        }
        return res.toString();
    }
}
    0 赞同 0 条回复
  • 阿尚 普通 2023年7月31日 下午8:38 
    //自定义排序
//使用快速排序
class Solution {
    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);

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

    public void quickSort(String[] strs, int l, int r){
        if(l >= r) return;

        int p = partition(strs, l, r);

        quickSort(strs, l, p - 1);
        quickSort(strs, p + 1, r);
    }

    public int partition(String[] strs, int l, int r){

        int i = l;
        int j = r;

        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++;
            swap(strs, i, j);
        }
        swap(strs, i, l);
        return i;
    }

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

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

        return String.join("", strs);
    }
}
    0 赞同 0 条回复
  • mpweixin用户 普通 2023年7月31日 下午3:34 
    //输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。 
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 res = new StringBuilder();
            for(String s : strs)
                res.append(s);
            return res.toString();
        }
        void quickSort(String[] strs, int l, int r) {
            if(l >= r) return;
            int i = l, j = r;
            String tmp = strs[i];
            while(i < j) {
                while((strs[j] + strs[l]).compareTo(strs[l] + strs[j]) >= 0 && i < j) j--;
                while((strs[i] + strs[l]).compareTo(strs[l] + strs[i]) <= 0 && i < j) i++;
                tmp = strs[i];
                strs[i] = strs[j];
                strs[j] = tmp;
            }
            strs[i] = strs[l];
            strs[l] = tmp;
            quickSort(strs, l, i - 1);
            quickSort(strs, i + 1, r);
        }
    0 赞同 0 条回复

# 回答此问题

后才能回答