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

lQl 永久会员 2024年12月27日上午12:17

快排

class Solution {
    public String crackPassword(int[] password) {
        String result = "";
        String[] passwords = new String[password.length];
        for (int i = 0; i < password.length; i++) {
            passwords[i] = Integer.toString(password[i]);
        }
        Arrays.sort(passwords, (a, b) -> (a + b).compareTo(b + a));
        for (String psw : passwords) {
            result += psw;
        }
        return result;
    }
}

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

0 赞同 0 条回复

Xiang. 永久会员 2024年12月22日上午11:40

class Solution {
    public String crackPassword(int[] password) {
        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();
    }
    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);
    }
}
时间复杂度：O（nlogn）
空间复杂度：O（n）

0 赞同 0 条回复

陆狗陆狗普通 2024年12月19日上午1:15

解题思路
– 1、把int数组转换成string数组
– 2、两个字符组合，比如34和5 ，组成345 或者 534，一定是“小”的34在前面。以此类推到数组里面的所有元素，把“最大值”（此处的最大的判断标准不是用int去判断，而是通过组合数去判断的）放在最右边，把最小值放在最左边，转换成了一个排序问题
– 3、采用快排进行排序string数组
– 4、组合string数组成一个字符串
【题解1】

class Solution {
    public String crackPassword(int[] password) {
        // 1、把int数组转换成string数组
        // 2、两个字符组合，比如34和5 ，组成345 或者
        // 534，一定是“小”的34在前面。以此类推到数组里面的所有元素，把“最大值”（此处的最大的判断标准不是用int去判断，而是通过组合数去判断的）放在最右边，把最小值放在最左边，转换成了一个排序问题
        // 3、采用快排进行排序

        // int数组转换成string数组
        String[] array = new String[password.length];
        for (int i = 0; i < password.length; i++) {
            array[i] = String.valueOf(password[i]);
        }
        // 快排
        quickSort(array, 0, array.length - 1);
        // 打印数字
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < array.length; i++) {
            builder.append(array[i]);
        }
        return builder.toString();

    }

    public void quickSort(String[] array, int leftIndex, int rightIndex) {
        if (leftIndex >= rightIndex) {
            return;
        }
        // 【错误点】需要保存原始的下标给子数组使用，否则会导致堆栈溢出
        // 保存原始的leftIndex、rightIndex为子数组中使用
        int i = leftIndex;
        int j = rightIndex;
        // 标准点
        String fix = array[leftIndex];
        while (leftIndex < rightIndex) {
            // 右边找出第一个比标准点小的值，交换到左边
            // 进入循环的条件是，比标准点大的值，即 rightfix>=fixright
            // 【错误点】比较是compare而不是compareTo方法
            while (leftIndex < rightIndex && (array[rightIndex] + fix).compareTo(fix + array[rightIndex]) >= 0) {
                rightIndex--;
            }
            // 执行交换，右边的点交换到左边leftIndex的位置
            if (leftIndex < rightIndex) {
                array[leftIndex] = array[rightIndex];
            }
            // 左边找出第一个比标准点大的值，交换到右边
            // 进入循环的条件是，比标准点小的值，即 leftfix<=fixleft
            while (leftIndex < rightIndex && (array[leftIndex] + fix).compareTo(fix + array[leftIndex]) <= 0) {
                leftIndex++;
            }
            // 执行交换，左边的点交换到右边的rightIndex的位置
            if (leftIndex < rightIndex) {
                array[rightIndex] = array[leftIndex];
            }
        }
        // leftIndex=rightIndex的位置放标准点
        array[leftIndex] = fix;
        // 继续进行左子数组进行排列，右子数组进行排列
        // 【错误点】 子数组需要用i和j而不0和array.length-1
        quickSort(array, i, leftIndex - 1);
        quickSort(array, leftIndex + 1, j);
    }
}

错误点1：快排的函数需要保存原始的下标给子数组使用，否则会导致堆栈溢出
错误点2：字符串比较是compare而不是compareTo方法
错误点4：子数组需要用i和j而不0和array.length-1

0 赞同 0 条回复

秋山丽奈普通 2024年12月17日下午8:13

思路：使用冒泡排序的方式对数组进行处理，

class Solution {
    public String crackPassword(int[] password) {
        // 使用 冒泡排序 处理 
        int len = password.length;

        String[] str = new String[len];
        for(int i = 0; i < len; i ++){
            str[i] = String.valueOf(password[i]);
        }

        for(int i = 0; i < len; i ++){
            for(int j = 0; j < len - i - 1; j ++){
                if((str[j] + str[j+1]).compareTo(str[j+1] + str[j]) >= 0){
                    swap(str, j, j+1);
                }
            }
        }

        String ans = "";
        for(String temp: str){
            ans += temp;
        }

        return ans;

    }

    public void swap(String[] nums,int a,int b){
        String temp = nums[a];
        nums[a] = nums[b];
        nums[b] =temp;
        return;
    }
}

0 赞同 0 条回复

苯庸普通 2024年12月17日下午4:06

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

}

void quickSort(String[] strs, int l, int r){
    if(l >= r) return;
    int i = l-1, j = r+1;
    String pivot = strs[l];
    while(i < j){
        do i++; while((strs[i] + pivot).compareTo(pivot + strs[i]) < 0);
        do j--; while((strs[j] + pivot).compareTo(pivot + strs[j]) > 0);
        if(i >= j){
            break;
        }
        String temp = strs[i];
        strs[i] = strs[j];
        strs[j] = temp;
    }
    quickSort(strs, l, j);
    quickSort(strs, j+1, r);
}

}
时间：O（lgn）
空间：O（n）

0 赞同 0 条回复

迢迢星野普通 2024年12月16日下午9:05

class Solution {
/**
     * 闯关游戏需要破解一组密码，闯关组给出的有关密码的线索是：
     *      一个拥有密码所有元素的非负整数数组 password
     *      密码是 password 中所有元素拼接后得到的最小的一个数
     * 请编写一个程序返回这个密码。
     * 
     * 题意解读：转换为字符串拼接后，最小的
     * 
     * @param password 密码数组，包含组成密码的非负整数元素
     * @return 返回拼接后得到的最小数的字符串形式
     */
    public String crackPassword(int[] password) {
        // 将整数数组转换为字符串列表，便于后续处理
        List<String> strList = new ArrayList<>();
        for (int num : password) {
            strList.add(String.valueOf(num));
        }

        // 自定义排序规则，使得拼接后的字符串最小
        strList.sort((s1, s2) -> (s1 + s2).compareTo(s2 + s1));

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

        // 返回拼接后的最小数的字符串形式
        return sb.toString();
    }
}

思路：转换为字符串进行拼接，比较大小
时间复杂度：O(n)
空间复杂度：O(n)

0 赞同 0 条回复

晓宇普通 2024年12月16日下午5:01

class Solution {
public:
    // 快速排序 x + y > y + x swap(x,y)
    string crackPassword(vector& password) {
        if(password.empty()) return "";
        vector strs(password.size());
        string ans = "";
        for(int i = 0; i < password.size(); i++)
            strs[i] = to_string(password[i]);
        quick_sort(strs, 0, strs.size());
        for(int i = 0; i < password.size(); i++)
            ans += strs[i];
        return ans;
    }


void quick_sort(vector &arr,int l, int r){
    if(r - l <= 2){
        if(r - l < 2) return ;
        else if(arr[l] + arr[l + 1] > arr[l + 1] + arr[l])  swap(arr,l ,l + 1);
    }

    string pivot = arr[l]; 
    int x = l, y = r - 1;

    while (x < y) {
        while (x < y && (arr[y] + pivot) >= (pivot + arr[y]))  --y;
        if(x < y) arr[x++] = arr[y];
        while (x < y && (arr[x] + pivot) <= (pivot + arr[x]))   ++x;
        if(x < y) arr[y--] = arr[x];

    }

    arr[x] = pivot;
    quick_sort(arr, l, x);
    quick_sort(arr, x + 1, r);
}

void swap(vector arr, int idx, int idy){
    __typeof(arr[idx]) __c = arr[idx];
    arr[idx] = arr[idy];
    arr[idy] = __c;
}
// o(nlogn) o(n)


};

0 赞同 0 条回复

Aatorx 永久会员 2024年12月16日下午3:51

class Solution {
public:
    string crackPassword(vector<int>& password) {
        string s;
        vector<string> v;
        for (int i = 0; i < password.size(); i++) {
            v.push_back(to_string(password[i]));
        }
        sort(v.begin(), v.end(), [](string& x, string& y){return x + y < y + x;});
        for(int i = 0; i < v.size(); i++) {
            s += v[i];
        }
        return s;
    }
};

自定义排序规则，若x+y<y+x，则x<y。
时间复杂度O(Nlogn)，空间复杂度O(N)。

0 赞同 0 条回复

月下足迹普通 2024年12月16日上午11:18

//内置算法自定义排序
class Solution {
public String crackPassword(int[] password) {
int n = password.length;
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 res = new StringBuilder();
for(String s : strs)
res.append(s);
return res.toString();
}
}

0 赞同 0 条回复

jaron 普通 2024年12月15日上午10:17

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

    // 快速排序
    public void quickSort(String[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        // 随机选一个pivot
        String x = arr[l + (int) (Math.random() * (r - l + 1))];
        partition(arr, l, r, x);
        int left = first;
        int right = last;
        quickSort(arr, l, left - 1);
        quickSort(arr, right + 1, r);
    }

    public static int first, last;

    public static void partition(String[] arr, int l, int r, String x) {
        first = l;
        last = r;
        int i = l;
        while (i <= last) {
            // 比较arr[i] + x和x + arr[i]
            if ((arr[i] + x).compareTo(x + arr[i]) == 0) {
                i++;
            } else if ((arr[i] + x).compareTo(x + arr[i]) < 0) {
                swap(arr, first++, i++);
            } else {
                swap(arr, i, last--);
            }
        }
    }

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

0 赞同 0 条回复

Kisara 普通 2024年12月14日下午8:19

用快排完成,无非就是将大小比较变成拼接后的字符串比较

class Solution {
    public String crackPassword(int[] password) {
        String[] strs=new String[password.length];
        for(int i=0;i<password.length;i++)
        {
            strs[i]=String.valueOf(password[i]);
        }   
        quickSort(strs,0,password.length-1);
        StringBuilder builder =new StringBuilder();
        for(String n:strs){
            builder.append(n);
        }

        return builder.toString();
    }

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

        String pivot=strs[high];
        int i=low-1;
        for(int j=low;j<high;j++){
            if((strs[j]+pivot).compareTo(pivot+strs[j])<=0){
                i++;
                String temp=strs[i];
                strs[i]=strs[j];
                strs[j]=temp;
            }
        }
        String temp=strs[i+1];
        strs[i+1]=strs[high];
        strs[high]=temp;

        quickSort(strs,low,i);
        quickSort(strs,i+2,high);

    }


}

On ON

0 赞同 0 条回复

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

共以下 11 个回答

# 回答此问题取消回复

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

共以下 11 个回答

# 回答此问题 取消回复

# 回答此问题取消回复