45.把数组排成最小的数

raylan.chen大约 2 分钟

尝试使用回溯列出所有结果，但是超时了

class Solution {
    List<String> list;
    boolean[] flag;
    String min;
    public String crackPassword(int[] password) {
        if (password == null || password.length == 0) return "";

        // 回溯
        list = new ArrayList<>();
        flag = new boolean[password.length];
        recursion(password);
        return min;
    }

    public void recursion(int[] password) {
        //终止条件
        if (list.size() == password.length) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < list.size(); i++) {
                sb.append(list.get(i));
            }
            
            String tmp = sb.toString();
            if (min == null) {
                min = tmp;
                return;
            }
            if (tmp.compareTo(min) < 0) min = tmp;

            return;
        }

        for (int i = 0; i < password.length; i++) {
            if (flag[i] == true) continue;
            list.add(String.valueOf(password[i]));
            flag[i] = true;
            recursion(password);
            list.remove(list.size() - 1);
            flag[i] = false;
        }
    }
}

优秀题解

还是快排大法好呀！

class Solution {
public:
    string minNumber(vector<int>& nums) {
        // 快速排序
        int len = nums.size();
        vector<string> ans;
        for (auto num : nums) ans.push_back(to_string(num));
        sort(ans, 0, len - 1);
        string ret = "";
        for (auto str : ans) ret += str;
        return ret;
    }

    void sort(vector<string>& ans, int left, int right){
        if (right <= left) return;
        int j = partition(ans, left, right);
        sort(ans, left, j - 1);
        sort(ans, j + 1, right);
    }
    
    // 切分
    int partition(vector<string>& ans, int left, int right){
        int i = left, j = right;
        string pivot = ans[left];
        while (true){
            while (ans[i] + pivot <= pivot + ans[i]){
                if (++i > j) break;
            }
            while (pivot + ans[j] < ans[j] + pivot){
                if (--j < i) break;
            }
            if (i >= j) break;
            string tmp = ans[i];
            ans[i] = ans[j];
            ans[j] = tmp;
        }
        string tmp = ans[left];
        ans[left] = ans[j];
        ans[j] = tmp;
        return j;
    }
};

作者：Dormiveglia
链接：https://leetcode.cn/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/solutions/1430542/by-dormiveglia_zachary-5dqj/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

自己也尝试写了一遍

class Solution {
    public String crackPassword(int[] password) {
        if (password == null || password.length == 0) return "";
        String[] nums = new String[password.length];
        for (int i = 0; i < password.length; i++) {
            nums[i] = String.valueOf(password[i]);
        }
        sort(nums, 0, nums.length - 1);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < nums.length; i++) {
            sb.append(nums[i]);
        }
        return sb.toString();
    }

    public void sort(String[] nums, int start, int end) {
        //终止条件
        if (start >= end) return ;

        String base = nums[start];
        int i = start; 
        int j = end;
        while (i < j) {
            while (j > i && (base + nums[j]).compareTo(nums[j] + base) <= 0) j--;
            nums[i] = nums[j];
            while (i < j && (base + nums[i]).compareTo(nums[i] + base) >= 0) i++;
            nums[j] = nums[i];
        }
        nums[i] = base;

        sort(nums, start, i - 1);
        sort(nums, i + 1, end);
    }
}

45.把数组排成最小的数

45.把数组排成最小的数

参考链接

个人尝试

优秀题解