【排序算法运用】剑指 Offer 45. 把数组排成最小的数-跟着帅地玩副业，开拓第二曲线PlayOffer

Gg 普通 2023年6月25日下午11:11

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,(s1,s2)-> (s1 + s2).compareTo(s2 + s1));
        StringBuilder sb = new StringBuilder();
        for(String str : strs){
            sb.append(str);
        }
        return sb.toString();
    }
}

0 赞同 0 条回复

宁永久会员 2023年3月15日下午4:04

快速排序，注意检查下标

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]);
        }
        sort(strs, 0, strs.length - 1);
        StringBuilder stringBuilder = new StringBuilder();
        for(int i = 0; i < strs.length; i++){
            stringBuilder.append(strs[i]);
        }
        return stringBuilder.toString();
    }
    public static void sort(String[] arr, int start, int end){
        if (start >= end) return;
        int l = start, r = end;
        while (l < r){
            while(l < r && (arr[start] + arr[r]).compareTo(arr[r] + arr[start]) <= 0){
                r--;
            }
            while (l < r && (arr[l] + arr[start]).compareTo(arr[start] + arr[l]) <= 0){
                l++;
            }
            if (l < r){
                String temp = arr[l];
                arr[l] = arr[r];
                arr[r] = temp;
            }
        }
        String temp = arr[start];
        arr[start] = arr[l];
        arr[l] = temp;
        sort(arr, start, l - 1);
        sort(arr, l + 1, end);
    }
}

0 赞同 0 条回复

lucca 普通 2023年1月15日下午11:32

快排思想

时间复杂度 O(NlogN)
空间复杂度 O(N)

class Solution {
    public String minNumber(int[] nums) {
        int n = nums.length;
        String[] s = new String[n];
        for (int i = 0; i < n; i++)
            s[i] = Integer.toString(nums[i]);

        sort(s, 0, n - 1);
        StringBuilder sb = new StringBuilder();
        for (String str : s) sb.append(str);
        return sb.toString();
    }

    private void sort(String[] s, int l, int r) {
        if (l >= r) return;

        String x = s[l + r >> 1];
        int i = l - 1, j = r + 1;
        while (i < j) {
            do { i++; } while ((s[i] + x).compareTo(x + s[i]) < 0);
            do { j--; } while ((s[j] + x).compareTo(x + s[j]) > 0);
            if (i < j) {
                String t = s[i];
                s[i] = s[j];
                s[j] = t;
            }
        }

        sort(s, l, j);
        sort(s, j + 1, r);
    }
}

0 赞同 0 条回复

PatNick 普通 2023年1月13日下午5:25

class Solution:
    def minNumber(self, nums: List[int]) -> str:
        left = 0
        right = len(nums) - 1
        if len(nums) == 1:
            return str(nums[0])
        # 快排
        self.quickSort(nums,left,right)
        nums_str = [str(_) for _ in nums]
        return "".join(nums_str)


    def quickSort(self,arr,left,right):
        if left > right:
            return

        m = self.partition(arr,left,right)
        self.quickSort(arr,left,m-1)
        self.quickSort(arr,m+1,right)



    def partition(self,arr,left,right):
        # 中间值
        middle = arr[left]

        # 初始化左右边界
        i = left
        j = right

        while i < j:
            while i <= j and int(str(middle)+str(arr[i])) >= int(str(arr[i])+str(middle)):
                i += 1
            while i <= j and int(str(middle)+str(arr[j])) <= int(str(arr[j])+str(middle)):
                j -= 1

            if i >= j:
                break

            temp = arr[j]
            arr[j] = arr[i]
            arr[i] = temp

        # 此时i = j，已经分成了两部分
        # 将middle基准值放到i的位置上
        arr[left] = arr[j]
        arr[j] = middle

        return j

0 赞同 0 条回复

yanshuojune 普通 2022年12月7日下午10:57

时间：O（NlogN）
空间：O(N)

class Solution:
    def minNumber(self, nums: List[int]) -> str:
        def sort(x, y):
            a = x + y
            b = y + x
            if a > b:
                return 1
            elif a < b:
                return -1
            else:
                return 0
        nums_str = [str(num) for num in nums]
        nums_str.sort(key=functools.cmp_to_key(sort))
        return ''.join(nums_str)

0 赞同 0 条回复

是梦终空永久会员 2022年12月7日下午3:52

时间O(nlogn)
空间O(n)

class Solution {
    public String minNumber(int[] nums) {
        int len = nums.length;
        String[] strs = new String[len];
        for(int i = 0;i<len;i++){
            strs[i] = String.valueOf(nums[i]);
        }
        quickSort(strs,0,len-1);
        StringBuilder res = new StringBuilder();
        for(String s:strs){
            res.append(s);
        }
        return res.toString();
    }
    public void quickSort(String[] strs,int r,int l){
       if(l >= r) return;
        int i = l, j = r;
        String temp = 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++;
            temp = strs[i];
            strs[i] = strs[j];
            strs[j] = temp;
        }
        strs[i] = strs[l];
        strs[l] = temp;
        quickSort(strs, l, i - 1);
        quickSort(strs, i + 1, r);
    }

}

0 赞同 0 条回复

symbol 普通 2022年12月3日上午7:38

func minNumber(nums []int) string {
    //将整数数组按字符串形式排序
    sort.Slice(nums, func(i, j int) bool {
        x := fmt.Sprintf("%d%d", nums[i], nums[j]) // 字符拼接
        y := fmt.Sprintf("%d%d", nums[j], nums[i])
        return x < y
    })

    res := ""
    for i:=0; i<len(nums); i++ {
        res += fmt.Sprintf("%d", nums[i])
    }
    return res
}

0 赞同 0 条回复

🚲南下普通 2022年12月2日下午5:47

class Solution {
public:
    static bool compare(string s1, string s2){ //自定义比较函数
        return s1+s2 < s2+s1; //字符串大于，同时为数字也是大于的
    }

    string minNumber(vector<int>& nums) {
        vector<string> res;
        for(auto s: nums){
            string temp = to_string(s);
            res.push_back(temp);
        }

        sort(res.begin(),res.end(),compare);
        string result;
        for(auto s: res){
            result+=s;
        }
        return result;

    }
};

0 赞同 0 条回复

波波_1936 普通 2022年11月24日下午7:09

/**
     * 面试题45. 把数组排成最小的数
     * @param nums
     * @return
     */
    public String minNumber(int[] nums) {
        //时间复杂度O(nlgn)
        //空间复杂度O(n)
        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 sb = new StringBuilder();
        for (int i = 0; i < strs.length; i++) {
            sb.append(strs[i]);
        }
        return sb.toString();
    }

0 赞同 0 条回复

你有点可爱喔普通 2022年11月24日下午3:27

时间复制度O(nlogn)

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();
    }


    public void quickSort(String [] str,int L,int R){
        if (L > R) {
            return;
        }
        int i = partition(str,L,R);
        quickSort(str, L, i - 1);
        quickSort(str, i + 1, R);
    }

      public int partition(String[] str, int L, int R) {
        String pivot = str[L];
        int left = L, right = R;
        while (left < right) {
            while (left <= right && (str[left] + pivot).compareTo(pivot + str[left]) <= 0) {
                left++;
            }
            while (left <= right && (str[right] + pivot).compareTo(pivot + str[right]) >= 0) {
                right--;
            }
            if (left >= right) {
                break;
            }
            String temp = str[left];
            str[left] = str[right];
            str[right] = temp;
        }
        str[L] = str[right];
        str[right] = pivot;
        return right;
    }
}

0 赞同 0 条回复

y 普通 2022年11月23日下午9:23

var minNumber = function(nums) {
    quickSort(nums,0,nums.length-1);
    return nums.join('')
};

function compare(a,b){
    let s1 = a +  '' + b;
    let s2 = b +  '' + a;
    return s1 > s2 ? true : false;

}

function quickSort(nums, l, r){
    if(l >= r){
        return;
    }
    //i索引，num[i]已经是左边小于num[i],右边大于num[i];
    let i = partition(nums, l, r);
    //以i为分割点
    quickSort(nums, l, i-1);
    quickSort(nums, i+1, r);
}

function partition(nums, l, r){
    let pivot = nums[l];
    let i = l + 1;//从1开始，
    let j = r;
    while(i<=j){
        while(i<=j && compare(pivot,nums[i])){
            i++;
        }
        while(i<=j && compare(nums[j],  pivot)){
            j--;
        }
        if(i<=j){
            let temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
            i++;
            j--;
        }
    }
    //交换pivot和num[j]
    nums[l] = nums[j];
    nums[j] = pivot;
    return j;

}

0 赞同 0 条回复

@ 普通 2022年11月22日上午11:33

思路：快排
时间复杂度O(N logN)
空间复杂度 O(n)

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 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 p = partition(strs, l, r);
        quickSort(strs, l, p - 1);
        quickSort(strs, p + 1, r);
    }

    private  int partition(String[] strs, int l, int r){
        int i = l, j = r;
        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++;
            swap(strs, i, j);
        }
        swap(strs, j, l);

        return j;


    }

    private void swap(String[] nums, int l, int r) {
        String t = nums[l];
        nums[l] = nums[r];
        nums[r] = t;
    }
}

0 赞同 0 条回复

天然普通 2022年11月21日下午10:33

a+b>b+a

class Solution:
    def minNumber(self, nums: List[int]) -> str:
        if not nums: return nums
        res  = [str(m) for m in nums]
        num = len(res)
        for i in range(num):
            for j in range(0,num-1-i):
                if res[j]+ res[j+1] > res[j+1]+res[j]:
                    res [j+1] , res[j] = res[j] , res[j+1]
        return ''.join(res)

class Solution:
    def minNumber(self, nums: List[int]) -> str:
        def f_sort(x,y):
            a , b = x+y,y+x
            if a > b: return 1
            elif a< b: return -1
            else: return 0
        nums = [str(m) for m in nums]
        nums.sort(key= functools.cmp_to_key(f_sort))
        return ''.join(nums)    
时间复杂度O(nlogn),空间复杂度O(n)  用内置函数好想

0 赞同 0 条回复

lobort 普通 2022年11月21日下午5:13

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



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

    public static int partition(String[] nums, int left, int right){
        String p = nums[left];
        int less = left;
        int more = right;
        while(less < more){
            while(less <= more && ((nums[less] + p).compareTo(p + nums[less])) <= 0){
                less++;
            }
            while(less <= more && (nums[more] + p).compareTo(p + nums[more]) >= 0){
                more--;
            }
            if(less >= more){
                break;
            }
            String temp = nums[less];
            nums[less] = nums[more];
            nums[more] = temp;
        }
        nums[left] = nums[more];
        nums[more] = p;
        return more;
    }
}

没看懂

0 赞同 0 条回复

派大星普通 2022年11月19日下午7:34

class Solution {
//可以使用冒泡排序的方法，把数组按大小顺序排列出来；也可以使用快速排序的方法，按照一个点分为左右两侧，再用递归的方法
//使整个数组都变的稳定
//时间复杂度O(nlogn)
//空间复杂度O(n)
    public String minNumber(int[] nums) {
        if(nums == null || nums.length == 0) return "";
        String[] str = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            str[i] = nums[i] + "";
        }
        quickSort(str,0,str.length - 1);
        StringBuffer sb = new StringBuffer();
        for (String s : str) {
            sb.append(s);
        }
        return sb.toString();
    }
    public void  quickSort(String[] nums,int l,int r){
        if(l > r)return;
        int i = sort(nums,l,r);
        quickSort(nums,l,i - 1);
        quickSort(nums,i + 1,r);
    }
    public int sort(String[] nums,int l,int r){
        String middle = nums[l];
        int left = l;
        while(l < r){
            while(l <= r && (nums[l] + middle).compareTo(middle + nums[l]) <= 0) l++;
            while(l <= r && (nums[r] + middle).compareTo(middle + nums[r]) >= 0) r--;
            if(l >= r) break;
            String temp = nums[l];
            nums[l] = nums[r];
            nums[r] = temp;
        }
        nums[left] = nums[r];
        nums[r] = middle;
        return r;

    }
}

0 赞同 0 条回复

mpweixin用户普通 2022年11月17日下午5:27

C++:
我这个就是暴力吧，我看数据长度才100。但是我有跟着视频练一下快排

class Solution {
public:
string minNumber(vector& nums) {
string ans;
int cnt = 0;
for(int i = 0; i < nums.size(); ++i) {
if(nums[i] 0) {
cnt++;
continue;
}
for(int j = i+1; j < nums.size(); ++j) {
if(org(nums[i], nums[j])) swap(nums[i], nums[j]);
}
}
for(int i = 0; i < cnt; ++i) {
ans += to_string(0);
}
for(int i = 0; i < nums.size(); ++i) {
printf(“%d\t”, nums[i]);
if(nums[i] 0) continue;
ans += to_string(nums[i]);
}
return ans;
}

bool org(int m, int n) {
    string str1 = intToString(m, n);
    string str2 = intToString(n, m);
    return stringToInt(str1) > stringToInt(str2);
}
string intToString(int m, int n) {
    string strm;
    string strn;
    int t;
    int k = 10;
    while(m > 0) {
        t = m%k;
        m /= 10;
        strm += t;
    }
    reverse(strm.begin(), strm.end());
    while(n > 0) {
        t = n%k;
        n /= 10;
        strn += t;
    }
    reverse(strn.begin(), strn.end());
    return strm+strn;
}
long long stringToInt(string str) {
    long long ans = 0;
    for(int i = 0; i < str.size()-1; ++i) {
        ans += str[i];
        ans *= 10;
    }
    ans += str[str.size()-1];
    return ans;
}

};

0 赞同 0 条回复

So 普通 2022年11月17日上午11:24

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();
    }

    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(nlog(n))，空间：O(n)

0 赞同 0 条回复

訁訁訁訁訁普通 2022年11月17日上午11:06

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

/**
本质上是一个排序问题，假设字符串分别为x，y
若x + y < y + x 则 xy组合出的数字更小，x应该排在前面
若x + y > y + x 则 yx组合出的数字更小，y应该排前面
对数组中任意两个元素进行比较排列，就可以对整个数组得到最小排序
 */
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]);
        }
        Arrays.sort(s,(o1,o2)->(o1+o2).compareTo(o2+o1));
        return String.join("",s);
    }
}

手动实现快排

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]);
        }
        //Arrays.sort(s,(o1,o2)->(o1+o2).compareTo(o2+o1));
        quickSort(s,0,s.length-1);
        return String.join("",s);
    }
    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 条回复

T 普通 2022年11月17日上午11:03

快排实现

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]);
        }
        sort(strs, 0, nums.length - 1);
        StringBuilder res = new StringBuilder();
        for(String s : strs) {
            res.append(s);
        }
        return res.toString();
    }

    public void sort(String[] strs, int l, int r) {
        if(l < r) {
            int position = partition(strs, l, r);
            sort(strs, l, position - 1);
            sort(strs, position + 1, r);
        }
    }

    public int partition(String[] strs, int l, int r) {
        String pivot = strs[r];
        int pointer = l;
        for(int i = l; i < r; i++) {
            if((strs[i] + pivot).compareTo(pivot + strs[i]) < 0) {
                String tmp = strs[i];
                strs[i] = strs[pointer];
                strs[pointer] = tmp;
                pointer++;
            }
        }
        String tmp = strs[pointer];
        strs[pointer] = strs[r];
        strs[r] = tmp;
        return pointer;
    }
}

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年11月16日下午11:47

时间复杂度为O（nlgn），空间复杂度为O（n）

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();
    }
     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);

     }
     private int partition(String[] arr, int left, int right){
         String p = arr[left];
         int i = left;
         int j = right;
         while(i < j){
             while(i <= j && (arr[i] + p).compareTo(p + arr[i]) <= 0){
                 i++;
             }
             while(i <= j && (arr[j] + p).compareTo(p + 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] = p;
         return j;
     }
}

0 赞同 0 条回复

青木普通 2022年11月16日下午11:25

/**
    自己写的比较辣就不放了。
    快排的思想和上一题很像，将左端视为比对的对象，将所有小于他的数放左边，大于他的数放右边
    当i==j时指向的是小于等于他的数，因此直接将他与左端互换位置，再递归运算

    时间O(nlogn)
    空间O(n)
 */

class Solution {
    public String minNumber(int[] nums) {
        String[] str = new String[nums.length];
        for(int i = 0; i < nums.length; i++)
            str[i] = String.valueOf(nums[i]);

        QuickSort(str, 0, str.length-1);
        StringBuilder ans = new StringBuilder();
        for(String s : str){
            ans.append(s);
        }
        return ans.toString();
    }

    public void QuickSort(String[] str, int l, int r){
        if(l >= r) return;
        int i=l, j=r;
        String tmp = str[i];
        while(i<j){
            while(i<j && (str[j]+str[l]).compareTo(str[l]+str[j]) >= 0) j--;
            while(i<j && (str[i]+str[l]).compareTo(str[l]+str[i]) <= 0) i++;
            tmp = str[i];
            str[i] = str[j];
            str[j] = tmp;
        } 
        str[i] = str[l];
        str[l] = tmp;
        QuickSort(str, l, i-1);
        QuickSort(str, i+1, r);
    }
}

0 赞同 0 条回复

Error 普通 2022年11月16日下午11:07

class Solution:
    def minNumber(self, nums: List[int]) -> str:
        nums = [str(n) for n in nums]
        n = len(nums)
        for i in range(n):
            for j in range(0, n - 1 - i):
                if nums[j] + nums[j + 1] > nums[j + 1] + nums[j]:
                        nums[j], nums[j+ 1] = nums[j+1], nums[j]
        return ''.join(nums)

冒泡排序
时间复杂度 log(n)

0 赞同 0 条回复

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

共以下 22 个回答

快排思想

# 回答此问题取消回复

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

共以下 22 个回答

快排思想

# 回答此问题 取消回复

# 回答此问题取消回复