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

小肸永久会员 2023年9月8日下午6:40

class Solution {
    //快速排序思路，时间复杂度为O(nlogn),n次递归调用，每一次递归调用的时间复杂度为O(logN)，
    //所以空间复杂度为O(N)
    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 str : strs) {
            res.append(str);
        }
        return res.toString();
    }
    private void quickSort(String[] strs, int left, int right) {
        if (left >= right) {
            return;
        }
        int i = left, j = right;
        String baseVal = strs[i];
        while (i < j) {
            //规定如果x+y > y + x，则 x "大于" y
            //如果x+y < y + x，则x "小于" y
            //找到右侧第一个小于基准值的元素
            while (i < j && (strs[j] + baseVal).compareTo(baseVal + strs[j]) >= 0) {
                j --;
            }
            //找到左侧第一个大于基准值的元素
            while (i < j && (strs[i] + baseVal).compareTo(baseVal + strs[i]) <= 0) {
                i ++;
            }
            if (i < j) {
                String tmp = strs[i];
                strs[i] = strs[j];
                strs[j] = tmp;
            }
        }
        strs[left] = strs[i];
        strs[i] = baseVal;
        quickSort(strs, left, i - 1);
        quickSort(strs, i + 1, right);
    }
}

0 赞同 0 条回复

别扒拉我普通 2023年9月7日上午12:33

快排思想

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 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 条回复

塔底的仰望永久会员 2023年9月6日下午12:37

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

class Solution {
    public String minNumber(int[] nums) {
        if (nums.length <= 1) {
            return String.valueOf(nums[0]);
        }
        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[] nums, int start, int end) {
        if (start > end) {
            return ;
        }
        int pivotpos = partition(nums, start, end);
        quickSort(nums, start, pivotpos - 1);
        quickSort(nums, pivotpos + 1, end);
    }

    public int partition(String[] nums, int start, int end) {
        String pivot = nums[start];
        int i = start;
        int j = end;

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

            if (i >= j) {
                break;
            }
            String temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        nums[start] = nums[j];
        nums[j] = pivot;

        return j;
    }
}

0 赞同 0 条回复

sincere 普通 2023年9月6日上午10:44

思路：用快排思想将字符排序，排序的规则是”x”+”y”<“y”+”x”则x在左边。也可以用优先队列构建一个小根堆Queue<String> queue = new PriorityQueue<>(new Comparator<String>(){....});，规则也是一样的
复杂度：时间复杂度O(Nlogn 快排logn遍历n)，空间复杂度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);
        //Arrays.sort(strs, (x, y) -> (x + y).compareTo(y + x));// 系统函数
        StringBuilder builder = new StringBuilder();
        for (String str : strs) {
            builder.append(str);
        }
        return builder.toString();
    }

    // "x+y"<"y+x"：说明字符形式x<y，x应该在y左边，快速排序
    void quickSort(String[] strs, int low, int high) {
        if (low >= high) {
            return;
        }
        int i = low, j = high;
        String tmp = strs[i];// 以第一个为基准值
        while (i < j) {
            while ((i < j) && (strs[j] + strs[low]).compareTo(strs[low] + strs[j]) >= 0) {
                j--;// 从后向前找比基准小的数
            }
            while ((i < j) && (strs[i] + strs[low]).compareTo(strs[low] + strs[i]) <= 0) {
                i++;// 从前向后找比基准大的数
            }
            tmp = strs[i];
            strs[i] = strs[j];
            strs[j] = tmp;
        }
        strs[i] = strs[low];// 中位和基准值交换
        strs[low] = tmp;
        quickSort(strs, low, i - 1);
        quickSort(strs, i + 1, high);
    }
}

0 赞同 0 条回复

行动派小彩笔普通 2023年9月5日下午10:34

// 快排思想，时间复杂度O(nlogn),空间复杂度O(n)
class Solution {
public:
    int partition(vector<string>& nums,int l,int r)
    {
        int pvoit = l;
        swap(nums[pvoit],nums[r]);
        int i=l;
        for(int j=l;j<r;++j)
        {
            if(nums[j]+nums[r]<nums[r]+nums[j])
            {
                swap(nums[j],nums[i]);
                ++i;
            }    
        }
        swap(nums[i],nums[r]);
        return i;
    }
    void quickSort(vector<string>& nums,int l,int r)
    {
        if(l>=r) return;
        int mid = partition(nums,l,r);
        quickSort(nums,l,mid-1);
        quickSort(nums,mid+1,r);
    }
    string minNumber(vector<int>& nums) {
        vector<string> vec;
        for(auto num:nums)
        {
            vec.push_back(to_string(num));
        }
        quickSort(vec,0,vec.size()-1);
        string res;
        for(auto num:vec)
        {
            res+=num;
        }
        return res;

    }
};

0 赞同 0 条回复

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

共以下 5 个回答

# 回答此问题取消回复

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

共以下 5 个回答

# 回答此问题 取消回复

# 回答此问题取消回复