(排序) 剑指 Offer 45. 把数组排成最小的数 ——【Leetcode每日一题】

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

❓ 剑指 Offer 45. 把数组排成最小的数

难度:中等

输入一个非负整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。

示例 1:

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

示例 2:

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

提示:

  • 0 < nums.length <= 100

说明:

  • 输出结果可能非常大,所以你需要返回一个字符串而不是整数
  • 拼接起来的数字可能会有前导 0,最后结果不需要去掉前导 0

💡思路:

可以看成是一个排序问题,在比较两个字符串 s1s2 的大小时,应该比较的是 s1+s2s2+s1 的大小:

  • 如果 s1+s2 < s2+s1,那么应该把 s1 排在前面,否则应该把 s2 排在前面。

总体流程:

  1. 初始化: 字符串列表 strs ,保存各数字的字符串格式;
  2. 列表排序: 应用以上 “排序判断规则” ,对 strs 执行排序;
  3. 返回结果: 拼接 strs 中的所有字符串,并返回。

法一:快速排序

需修改快速排序函数中的排序判断规则。字符串大小(字典序)对比的实现方法:

  • C++ 中可直接用 < , >
  • Java 中使用函数 A.compareTo(B)

法二:内置函数

  • C++ 定义为 (string& x, string& y){ return x + y < y + x; } ;
  • Java 定义为 (x, y) -> (x + y).compareTo(y + x);

🍁代码:(C++、Java)

法一:快速排序
C++

class Solution {
private:
    void quickSort(vector<string>& strs, int l, int r){
        if(l >= r) return;
        int i = l + 1, j = r;
        while(i <= j){
            //从前往后找第一个比str[l] 大的字符串
            while(i <= j && strs[i] + strs[l] <= strs[l] + strs[i])i++;
            //从后往前找第一个比str[l] 小的字符串
            while(i <= j && strs[j] + strs[l] >= strs[l] + strs[j])j--;
            //交换
            if(i < j)
                swap(strs[i++], strs[j--]);
        }
        swap(strs[l], strs[j]);
        quickSort(strs, l, j - 1);
        quickSort(strs, j + 1, r);
    }
public:
    string minNumber(vector<int>& nums) {
    	// 1. 初始化
        vector<string> strs;
        for(int i = 0; i < nums.size(); i++){
            strs.push_back(to_string(nums[i]));
        }
        // 2. 排序
        quickSort(strs, 0, strs.size() - 1);
        // 3. 返回结果
        string ans;
        for(string s : strs){
            ans.append(s);
        }
        return ans;
    }
};

Java

class Solution {
    private void quickSort(String[] strs, int l, int r){
        if(l >= r) return;
        int i = l + 1, j = r;
        String temp;
        while(i <= j){
            //从前往后找第一个比str[l] 大的字符串
            while(i <= j && (strs[i] + strs[l]).compareTo(strs[l] + strs[i]) <= 0)i++;
            //从后往前找第一个比str[l] 小的字符串
            while(i <= j && (strs[j] + strs[l]).compareTo(strs[l] + strs[j]) >= 0)j--;
            //交换
            if(i < j){
                temp = strs[i];
                strs[i++] = strs[j];
                strs[j--] = temp;
            }
        }
        //此时j + 1 = i,strs[i]左边的字符串一定比strs[l]小,strs[j]右边的字符串一定比strs[l]大
        temp = strs[l];
        strs[l] = strs[j];
        strs[j] = temp;
        quickSort(strs, l, j - 1);
        quickSort(strs, j + 1, r);
    }
    public String minNumber(int[] nums) {
    	// 1. 初始化
        String[] strs = new String[nums.length];
        for(int i = 0; i < nums.length; i++){
            strs[i] = String.valueOf(nums[i]);
        }
        // 2. 排序
        quickSort(strs, 0, strs.length - 1);
        // 3. 返回结果
        StringBuilder ans = new StringBuilder();
        for(String s : strs){
            ans.append(s);
        }
        return ans.toString();
    }
}

法二:内置函数
C++

class Solution {
public:
    string minNumber(vector<int>& nums) {
    	// 1. 初始化
        vector<string> strs;
        for(int i = 0; i < nums.size(); i++){
            strs.push_back(to_string(nums[i]));
        }
        // 2. 内置函数排序
        sort(strs.begin(), strs.end(), [](string& x, string& y){return x + y < y + x;});
        // 3. 返回结果
        string ans;
        for(string s : strs){
            ans.append(s);
        }
        return ans;
    }
};

Java

class Solution {
    public String minNumber(int[] nums) {
    	// 1. 初始化
        String[] strs = new String[nums.length];
        for(int i = 0; i < nums.length; i++){
            strs[i] = String.valueOf(nums[i]);
        }
        // 2. 内置函数排序
        Arrays.sort(strs, (x, y) -> (x + y).compareTo(y + x));
        // 3. 返回结果
        StringBuilder ans = new StringBuilder();
        for(String s : strs){
            ans.append(s);
        }
        return ans.toString();
    }
}
🚀 运行结果:

(排序) 剑指 Offer 45. 把数组排成最小的数 ——【Leetcode每日一题】,LeetCode,leetcode,算法,职场和发展

🕔 复杂度分析:
  • 时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn),其中 n 为数组的长度,使用快排或内置函数的平均时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn) ,最差为 O ( n 2 ) O(n^2) O(n2)
  • 空间复杂度 O ( n ) O(n) O(n),字符串列表 strs 占用线性大小的额外空间。

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!文章来源地址https://www.toymoban.com/news/detail-694575.html

注: 如有不足,欢迎指正!

到了这里,关于(排序) 剑指 Offer 45. 把数组排成最小的数 ——【Leetcode每日一题】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • Leetcode-每日一题【剑指 Offer 11. 旋转数组的最小数字】

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

    2024年02月14日
    浏览(41)
  • (排序) 剑指 Offer 51. 数组中的逆序对 ——【Leetcode每日一题】

    难度:困难 在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。 示例 1: 输入: [7,5,6,4] 输出: 5 限制 : 0 = 数组长度 = 50000 💡思路:归并排序 预备知识 「 归并排序 」是用 分治 思想,分

    2024年02月11日
    浏览(47)
  • (排序) 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面 ——【Leetcode每日一题】

    难度:简单 输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数在数组的前半部分,所有偶数在数组的后半部分。 示例: 输入:nums = [1,2,3,4] 输出:[1,3,2,4] 注:[3,1,2,4] 也是正确的答案之一。 提示 : 0 = n u m s . l e n g t h = 50000 0 = nums.length = 50000 0 =

    2024年02月12日
    浏览(50)
  • 每天一道leetcode:剑指 Offer 53 - I. 在排序数组中查找数字 I(适合初学者&二分查找)

    统计一个数字在排序数组中出现的次数。 0 = nums.length = 10^5 -10^9 = nums[i] = 10^9 nums 是一个非递减数组 -10^9 = target = 10^9 使用两次二分查找找到target在数组中的左右边界,然后长度就是右边界减去左边界再加一,最后返回长度即可。   欢迎大家在评论区讨论,如有不懂的代码部分

    2024年02月14日
    浏览(57)
  • 【剑指 offer】旋转数组的最小数字

    ✨个人主页:bit me👇 ✨当前专栏:算法训练营👇 核心考点:数组理解,二分查找,临界条件 描述: 有一个长度为 n 的非降序数组,比如[1,2,3,4,5],将它进行旋转,即把一个数组最开始的若干个元素搬到数组的末尾,变成一个旋转数组,比如变成了[3,4,5,1,2],或者[4,5,1,2,3]这

    2023年04月20日
    浏览(52)
  • 剑指offer面试题8 旋转数组的最小数字

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

    2024年01月24日
    浏览(39)
  • 剑指 Offer 53 - I. 在排序数组中查找数字 I

    题目来源 剑指 Offer 53 - I. 在排序数组中查找数字 I 初始化: 左边界 i=0 ,右边界 j=nums.length−1。 循环二分: 当闭区间 [i, j] 无元素时跳出; 计算中点 m=(i+j)/2 (向下取整); 若 nums[m]target,则 target 在闭区间 [m+1,j] 中,因此执行 i=m+1; 若 nums[m]target,则 target 在闭区间 [i,m−

    2024年02月01日
    浏览(41)
  • (数组与矩阵) 剑指 Offer 03. 数组中重复的数字 ——【Leetcode每日一题】

    难度:简单 找出数组中重复的数字。 在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。 示例 1: 输入 : [2, 3, 1, 0, 2, 5, 3] 输出 :2 或

    2024年02月16日
    浏览(39)
  • 【leetcode刷题之路】剑指Offer(4)——分治+排序算法+动态规划

    8 分治算法 8.1 【递归】剑指 Offer 07 - 重建二叉树 https://leetcode.cn/problems/zhong-jian-er-cha-shu-lcof/   前序遍历是根左右,中序遍历是左根右,这也就意味着前序遍历的第一个节点是整棵树的根节点,顺着这个节点找到它在中序遍历中的位置,即为in_root,那么in_root左边的都在左子

    2024年02月11日
    浏览(59)
  • (链表) 剑指 Offer 25. 合并两个排序的链表 ——【Leetcode每日一题】

    难度:简单 输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是递增排序的。 示例1: 输入:1-2-4, 1-3-4 输出:1-1-2-3-4-4 限制 : 0 = 链表长度 = 1000 注意:本题与 21. 合并两个有序链表 相同 💡思路: 法一:递归 将该问题可以分解成子链表,只比较当前 l1 链

    2024年02月15日
    浏览(45)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包