剑指 Offer 45. !!把数组排成最小的数(使用比较器的定制排序;快速排序)

这篇具有很好参考价值的文章主要介绍了剑指 Offer 45. !!把数组排成最小的数(使用比较器的定制排序;快速排序)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

剑指 Offer 45. 把数组排成最小的数
中等
662
相关企业
输入一个非负整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。

示例 1:

输入: [10,2]
输出: “102”
示例 2:

输入: [3,30,34,5,9]
输出: “3033459”

这道题在左程云算法课上讲过,但是这次做却完全没有印象了,只能大概想到需要排序。

方法一:使用内置排序函数
重点是:比较器的定义,这里使用lambda函数。

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 builder = new StringBuilder();
        for(String s:strs){
            builder.append(s);
        }
        return builder.toString();

    }
}

方法二:自己写一个快速排序
一篇非常棒的快速排序算法博文
注意快速排序算法的分析要区分理想情况和最坏情况。

时间复杂度 空间复杂度
理想情况 O ( n l o g n ) O(nlogn) O(nlogn) O ( l o g n ) O(logn) O(logn)
最坏情况 O ( n 2 ) O(n^2) O(n2) O ( n ) O(n) O(n)

注:文章来源地址https://www.toymoban.com/news/detail-619425.html

  1. 这里理想情况下的时间复杂度计算需要使用到Master公式(如果我没记错的话,应该是这名字,这个公式分析了递归函数内部调用子递归的次数等,推算出一个递归算法的时间复杂度。)
  2. 这里的空间复杂度是原地排序情况下的额外空间复杂度,主要是调用递归,使用了栈空间。
// 这里的代码参考了LeetCode评论区,谢谢大佬
 public String minNumber(int[] nums) {
        String[] strs = new String[nums.length];
        for(int i=0;i<nums.length;i++){
            strs[i] = Integer.toString(nums[i]);
        }
        quickSort(strs,0,strs.length-1);
        StringBuilder builder = new StringBuilder();
        for(String s:strs){
            builder.append(s);
        }
        return builder.toString();
    }
    public void quickSort(String[] strs, int low, int high){
        if(low<high){
            int middle = partition(strs,low,high);
            quickSort(strs,low,middle-1);
            quickSort(strs,middle+1,high);
        }

    }
    public int partition(String[] strs,int low, int high){
        String temp = strs[low];// chosen as pivot
        while(low<high){
            // must put this group "high--" ahead of that group "low++",先去处理右端,拿到右端的小值后,赋值到左端,再处理左端
       
             while(low<high && (strs[high]+temp).compareTo(temp+strs[high])>=0){// 注意这里是>=
                high--;
            }
            strs[low] = strs[high];  // 此时strs[low]已经被记录下来了(可能记录在temp,也可能在之前的strs[high]),所以可以被覆盖   
            while(low<high && (strs[low]+temp).compareTo(temp+strs[low])<=0){
                low++;
            }
            strs[high]=strs[low];
                  
        }
        strs[low]=temp;// 此时low指针来到“等于区”“中间区”
        return low;// 返回pivot的位置,此时strs中的当前段的左边都是“小于”pivot,右边都是“大于”pivot的
    }

到了这里,关于剑指 Offer 45. !!把数组排成最小的数(使用比较器的定制排序;快速排序)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 剑指offer面试题8 旋转数组的最小数字

    分析 首先一定要记住只要看到排序数组的查找,思维一定要往二分法上靠,然后再思考清楚如何利用二分法。而如何利用二分法一定要仔细分析所给的数组的特点:递增数组且最开始的若干元素搬到数组的末尾,相当于该数组由俩个递增小数组构成,前面的数组元素肯定大于

    2024年01月24日
    浏览(38)
  • 剑指 Offer 11. && LeetCode 154. 旋转数组的最小数字

    参考资料:LeetCode 官方解答 剑指 Offer 11. 旋转数组的最小数字 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 给你一个可能存在 重复 元素值的数组 numbers ,它原来是一个升序排列的数组,并按上述情形进行了一次旋转。请返回旋转数组的最小元素

    2024年02月09日
    浏览(40)
  • Leetcode-每日一题【剑指 Offer 11. 旋转数组的最小数字】

    把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 给你一个可能存在 重复 元素值的数组 numbers ,它原来是一个升序排列的数组,并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如,数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转,该数组的

    2024年02月14日
    浏览(39)
  • 从零学算法(剑指 Offer 45)

    输入一个非负整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。 示例 1: 输入: [10,2] 输出: “102” 示例 2: 输入: [3,30,34,5,9] 输出: “3033459” 我的原始人解法:直接冒泡排序,把最先应该拼接的那个数不断后移,然后拼接即可。关键就

    2024年02月10日
    浏览(36)
  • 【剑指 Offer 40】最小的k个数

    输入整数数组 arr ,找出其中最小的 k 个数。例如,输入 4、5、1、6、2、7、3、8 这 8 个数字,则最小的 4 个数字是 1、2、3、4。 示例: 输入:arr = [3,2,1], k = 2 输出:[1,2] 或者 [2,1] 输入:arr = [0,1,2,1], k = 1 输出:[0] 找到一个数组中最小的 k 个数,得出要对该数组进行排序 排序

    2024年02月13日
    浏览(35)
  • 剑指 Offer 66. 构建乘积数组

    给定一个数组 A[0,1,…,n-1] ,请构建一个数组 B[0,1,…,n-1] ,其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1] 。不能使用除法。 示例: 提示: 所有元素乘积之和不会溢出 32 位整数 a.length = 100000 解答

    2024年02月16日
    浏览(49)
  • 【剑指offer】数据结构——数组

    【剑指offer】03.数组中重复的数字 //03. 数组中重复的数字 // 找出数组中重复的数字。 // 力扣 // 在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。 // 数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每 // 个数字重复了几次。请找出数组中任意一

    2024年02月08日
    浏览(36)
  • 【剑指offer】数组中重复的数字

    👑专栏内容:力扣刷题 ⛪个人主页:子夜的星的主页 💕座右铭:前路未远,步履不停 剑指offer:数组中重复的数字 在一个长度为 n 的数组里的所有数字都在 0 0 0 到 n − 1 n-1 n − 1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复,也不知道每个数字重复了几

    2024年01月20日
    浏览(48)
  • 剑指 Offer —— 数组和字符串

    在一个 n * m 的二维数组中: 每一行都按照从左到右 非递减 的顺序排序 每一列都按照从上到下 非递减 的顺序排序 请完成一个高效的函数,输入这样的一个 二维数组和一个整数 ,判断 数组中是否含有该整数 。 示例: 现有矩阵 matrix 如下: 给定 target = 5 ,返回 true 。 给定

    2023年04月24日
    浏览(46)
  • 剑指 Offer 66. 构建乘积数组(中等)

    题目: 作者:Krahets 链接:https://leetcode.cn/problems/gou-jian-cheng-ji-shu-zu-lcof/solutions/208840/mian-shi-ti-66-gou-jian-cheng-ji-shu-zu-biao-ge-fe/ 来源:力扣(LeetCode)

    2024年02月10日
    浏览(31)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包