Loading [MathJax]/jax/output/CommonHTML/config.js
前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >妙呀,把数组排成最小的数!

妙呀,把数组排成最小的数!

作者头像
五分钟学算法
发布于 2022-01-05 00:08:33
发布于 2022-01-05 00:08:33
75700
代码可运行
举报
文章被收录于专栏:五分钟学算法五分钟学算法
运行总次数:0
代码可运行

大家新年好,我是吴师兄。

今天继续来学习《剑指Offer》系列的一道经典题目,依旧给出了非常详细的题解和精美的配图与动画。

一、题目描述

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

示例 1:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
输入: [10,2]
输出: "102"

示例 2:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
输入: [3,30,34,5,9]
输出: "3033459"

提示:

  • 0 < nums.length <= 100

说明:

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

二、解题思路

题目要求把数组中所有的数字一起拼凑出一个最小的数字,我们先来看几个例子,它们是如何得到那个最小的结果的。

首先来看示例 1

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
输入: [10,2]

对于 10 和 2 这两数来说,拼接的方式就两种:

  • 1、“ 10 ” + “ 2 ” = “ 102 ”
  • 2、“ 2 ” + “ 10 ” = “ 210 ”

102 是小于 210 的,也就意味着拼接过程中 10 应该放到 2 的前面。

那么,更一般的,对于两个数字 mn ,拼接的方式就两种:

  • 1、“ m ” + “ n ” = “ mn ”
  • 2、“ n ” + “ m ” = “ nm ”

最终,我们选取哪种方式取决于 mn 和 nm 的比较。

  • 1、当 mn < nm 时,选取 mn
  • 2、当 nm < mn 时,选取 nm

当理解清楚了上面的概念之后,再来看一个示例:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
输入: [3,30,34,1,9]

一开始 m = 3 ,n = 30,那么组成的字符串就是 “ 330 ”,如果将 m 和 n 交换一下,变成了 “303”,显然后者更小,意味着一开始 3 在前面 30 在后面这种方式是不对的,应该处理一下,让 30 放到前面而 3 放到后面

这里,我们提到了 前面后面 这个两个概念,那么肯定是要有中间部分的,这样才能区分前面、后面。

由此可以进一步的联想到,最终得到的那个最小的数字必然是可以划分为三个区域:左(前面)、中、右(后面)。

如上图所示,“ 1303349 ” 就是我们上述示例得到的最小数字,我们把红色看成左侧区域、蓝色看成中间区域、绿色看成右侧区域,这样划分之后具备如下的特征:

1、红色区域的任意数字和蓝色区域的任意数字进行拼接,都是会小于蓝色区域的任意数字和红色区域的任意数字进行拼接。

比如 1 和 3 拼接的结果小于了 3 和 1 拼接的结果。

比如 30 和 3 拼接的结果小于了 3 和 30 拼接的结果。

2、蓝色区域的任意数字和绿色区域的任意数字进行拼接,都是会小于绿色区域的任意数字和蓝色区域的任意数字进行拼接。

比如 3 和 34 拼接的结果小于了 34 和 3 拼接的结果。

比如 3 和 9 拼接的结果小于了 9 和 3 拼接的结果。

这就意味着,我们在寻找最小数字的过程中,实际上是在确定这三个区域的过程,而对于每个区域又同样可以不断的划分为左、中、右这个三个区域。

想到这个方向,实际上快速排序的概念应该能想到了,那我们来看一下是如果借助快速排序的方式解决这道题目的,具体操作如下:

1、题目说明输出结果可能非常大,需要返回一个字符串而不是整数,那么第一步就先把整型数组转换为字符串数组。

2、接下来开始对这个字符串数组进行排序操作。

3、选取第一个元素作为基准值,以这个基准值作为基础,先把字符串数组划分为三个部分:

  • 左边的部分和基准值进行拼接的字符串会小于基准值和左边的部分进行拼接的字符串
  • 基准值和右边的部分进行拼接的字符串会小于右边的部分和基准值进行拼接的字符串

先来看右边部分的 9 这个数字是否在正确的位置上。

此时,39 < 93,说明 9 应该在基准值 3 的右边部分,而现在在右边部分,那么 9 就先不用去处理,继续看其它的数字。

此时,31 > 13,说明 1 应该在基准值 3 的左边部分,而现在在右边部分,那么 1 应该挪到左边去,即挪到 left 指向的位置。

继续看其它的数字。

此时,303 < 330,说明 30 应该在基准值 3 的左边部分,而现在在左边部分,那么 30 就先不用去处理,继续看其它的数字。

此时,343 > 334,说明 34 应该在基准值 3 的右边部分,而现在在左边部分,那么 34 应该挪到右边去,即挪到 right 指向的位置。

通过如上的操作之后,整个字符串数组被划分为了三个区域:红色、蓝色、绿色。

这样划分之后具备如下的特征:

1、红色区域的任意数字和蓝色区域的任意数字进行拼接,都是会小于蓝色区域的任意数字和红色区域的任意数字进行拼接。

比如 1 和 3 拼接的结果小于了 3 和 1 拼接的结果。

比如 30 和 3 拼接的结果小于了 3 和 30 拼接的结果。

2、蓝色区域的任意数字和绿色区域的任意数字进行拼接,都是会小于绿色区域的任意数字和蓝色区域的任意数字进行拼接。

比如 3 和 34 拼接的结果小于了 34 和 3 拼接的结果。

比如 3 和 9 拼接的结果小于了 9 和 3 拼接的结果。

接下来,我们只需要按照同样的方法把红色区域也划分为三个区域、绿色区域也划分为三个区域,就可以得到一个最小的数字。

为了帮助你更好的理解整个过程,我特意做了一组动画,点开可以查看:

三、参考代码

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 剑指 Offer 45. 把数组排成最小的数:https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/
class Solution {
    public String minNumber(int[] nums) {

        // 先将 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 ans = new StringBuilder();

        for(String s : strs)
            ans.append(s);

        return ans.toString();
    }

    // 函数传入待排序数组 nums
    // 排序区间的左端点 left
    // 排序区间的右端点 right
    private void quickSort(String[] strs,int left, int right){

        // 如果 left 大于等于 right,说明该区间只有 1 个或者没有元素
        if( left >= right ){
            // 无需再递归划分后再排序,直接返回
            return;
        }

        // 调用函数 partition,将 left 和 right 之间的元素划分为左右两部分
        int mid = partition(strs,left,right);

        // 划分之后,再对 mid 左侧的元素进行快速排序
        quickSort(strs,left,mid - 1);

        // 划分之后,再对 mid 右侧的元素进行快速排序
        quickSort(strs,mid + 1,right);
    }

    // 直接套之前的快速排序的代码进行修改
    // 原先的小于的含义指的是数值上的小于,比如 1  < 10 
    // 但现在的小于含义为:a + b 拼凑的字符串小于 b + a 拼凑的字符串
    // 比如 a = 1 ,b = 10 
    // 那么 a + b = “110”,b + a = “101”
    // 显然,b + a < a + b
    // 也就是说 a 应该放到 b 的后面来拼凑字符串
    private int partition(String[] strs, int left ,int right){

        // 经典快速排序的写法
        // 设置当前区间的第一个元素为基准元素
        String pivot = strs[left];

        // left 向右移动,right 向左移动,直到 left 和 right 指向同一元素为止
        while( left < right ){

            // 当 pivot + strs[right] 的字符串小于 strs[right] + pivot 的字符串时
            // 说明 strs[right] 在正确的位置上,right 向左移动
            while( left < right && (pivot + strs[right]).compareTo(strs[right] + pivot) <= 0 ){
                // right 不断的向左移动
                right--;
            }

            // 此时,跳出了上面这个 while 循环,说明 pivot + strs[right] 的字符串大于 strs[right] + pivot 的字符串了
            // 说明 strs[right] 不在正确的位置上
            // 将此时的 strs[left] 赋值为 strs[right]
            // 执行完这个操作,比 pivot 小的这个元素被移动到了左侧
            strs[left] = strs[right];

            // 当 strs[left] + pivot 的字符串小于 pivot + strs[left] 的字符串时
            // 说明 strs[left] 在正确的位置上,left 向右移动
            while( left < right && (strs[left] + pivot).compareTo(pivot + strs[left]) <= 0){
                // left 不断的向右移动
                left++;
            }

            // 此时,跳出了上面这个 while 循环,说明 strs[left] + pivot 的字符串大于 pivot + strs[left] 的字符串了
            // 说明 strs[left] 不在正确的位置上
            // 将此时的 strs[right] 赋值为 strs[left]
            // 执行完这个操作,比 pivot 大的这个元素被移动到了右侧
            strs[right] = strs[left];

        }

        // 此时,left 和 right 相遇,那么需要将此时的元素设置为 pivot
        // 这个时候,pivot 的左侧元素都小于它,右侧元素都大于它
        strs[left] = pivot;

        // 返回 left
        return left;

    }
}

以上就是本期分享,有帮助的话还请给吴师兄一个点赞 + 在看 ,谢谢大家!

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2022-01-04,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 五分钟学算法 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
一道朴实无华的算法题:把数组排成最小的数
今天分享的题目来源于 LeetCode 上的剑指 Offer 系列 面试题45 把数组排成最小的数。
五分钟学算法
2020/07/02
9810
一道朴实无华的算法题:把数组排成最小的数
剑指offer | 面试题35:把数组排成最小的数
思路:此题求拼接起来的最小数字,本质上是一个排序问题。设数组nums中任意两数字的字符串为x和y,则规 定排序判断规则为:
千羽
2021/12/29
4330
剑指offer | 面试题35:把数组排成最小的数
LeetCode-面试题45-把数组排成最小的数
输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。
benym
2022/07/14
2740
剑指offer 33 把数组排成最小的数
转载请注明出处:http://blog.csdn.net/ns_code/article/details/28128551
bear_fish
2018/09/20
4850
最小的 k 个数!
今天继续来学习《剑指Offer》系列的一道经典题目,依旧给出了非常详细的题解和精美的配图与动画。
五分钟学算法
2022/02/18
4910
最小的 k 个数!
LeetCode通关:通过排序一次秒杀五道题,舒服!
大家好,我是拿输出博客督促自己刷题的老三,前面学习了十大排序:万字长文|十大基本排序,一次搞定!,接下来我们看看力扣上有没有什么能拿排序解决的题目吧!
三分恶
2021/09/10
8930
LeetCode通关:通过排序一次秒杀五道题,舒服!
剑指Offer题解 - Day35
输入一个非负整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。
chuckQu
2022/08/19
1900
每日一题《剑指offer》数组篇之把数组排成最小的数
输入一个非负整数数组numbers,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。
终有救赎
2023/10/16
1940
每日一题《剑指offer》数组篇之把数组排成最小的数
【算法】快速排序
【字符串】最长回文子串 ( 蛮力算法 ) 【字符串】最长回文子串 ( 中心线枚举算法 ) 【字符串】最长回文子串 ( 动态规划算法 ) ★ 【字符串】字符串查找 ( 蛮力算法 ) 【字符串】字符串查找 ( Rabin-Karp 算法 )
韩曙亮
2023/03/29
7900
【算法】快速排序
15分钟写不出快速排序的不考虑?!
快速排序首先选取一个数组元素作为基准(pivot),将小于pivot的放在左边,把大于pivot的放在右边,分割成两部分。再对其左右两部分进行排序。快排使用二分的思想将一个串分成两个子串,具体步骤如下:
才浅Coding攻略
2022/12/12
2230
15分钟写不出快速排序的不考虑?!
Leetcode No.75 颜色分类
给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。
week
2021/11/29
2950
一文搞定十大经典排序算法
下面我们来逐一分析十大经典排序算法,主要围绕下列问题展开: 1、算法的基本思想是什么? 2、算法的代码实现? 3、算法的时间复杂度是多少?(平均、最好、最坏)什么情况下最好?什么情况下最坏? 4、算法的空间复杂度是多少? 5、算法的稳定性如何?
matinal
2020/11/27
5910
一文搞定十大经典排序算法
深度解析之算法之分治(快排)
题目链接 给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ,原地 对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。
Undoom
2025/04/26
810
深度解析之算法之分治(快排)
常用的排序算法之快速排序(Quick Sort)
快速排序是由英国计算机科学家托尼·霍尔(Tony Hoare)在1960年提出的一种排序算法。它的基本思想是分治法(Divide and Conquer)的应用。
jack.yang
2025/04/05
1620
【优选算法篇】揭秘快速排序:分治算法如何突破性能瓶颈(上篇)
分治法是一种非常高效的算法设计策略,广泛应用于计算机科学的多个领域,尤其是在解决复杂问题时,它通过将大问题拆解成更小的子问题来降低问题的复杂度。快速排序(QuickSort)是分治法中的经典例子,能够在许多实际场景中提升性能。它的重要性体现在以下几个方面:
熬夜学编程的小王
2024/12/24
1110
【优选算法篇】揭秘快速排序:分治算法如何突破性能瓶颈(上篇)
重学数据结构和算法(五)之归并排序、快速排序
冒泡排序、插入排序、选择排序这三种排序算法,它们的时间复杂度都是 O(n2),比较高,适合小规模数据的排序。归并排序和快速排序的时间复杂度为 O(nlogn) 。这两种排序算法适合大规模的数据排序
六月的雨
2021/09/26
1.3K0
重学数据结构和算法(五)之归并排序、快速排序
八十一、最快最优的快速排序和优化
不久前,我在牛客中看到这样一个笑话,面试官让他写一个快速排序,结果他写了一个冒泡排序,虽说不是计算机专业的,还一直说没有写错,都不知道面试官为什么这么PASS。其实,一共有十大排序算法,最快最稳定的就是快速排序,简称快排。
润森
2022/08/17
6730
八十一、最快最优的快速排序和优化
极客算法训练笔记(六),十大经典排序之希尔排序,快速排序
排序算法的衡量指标我这里不再重复,上一篇我已经列举分析的很清楚了,但是非常重要,没看到我上一篇的小伙伴墙裂推荐,这里给一个直通车票 极客算法训练笔记(五),十大经典排序之冒泡,选择,插入排序 。
阿甘的码路
2020/11/12
4930
极客算法训练笔记(六),十大经典排序之希尔排序,快速排序
快速排序思想解决水桶问题
假设给你n个红色的水壶和n个蓝色的水壶。它们的形状和尺寸都各不相同。所有的红色水壶盛水量都各不相同,蓝色水壶也是如此。但对于每一个红色水壶来说,都有一个蓝色水壶盛水量和其相同;反之亦然。 你的任务是配对出全部盛水量相同的红色水壶和蓝色水壶。为此,可以执行的操作为,挑出一对水壶,一只红色一只蓝色,将红色水壶灌满水,将红色水壶的水倒入蓝色水壶中,看其是否恰好灌满来判断,这个红色水壶的盛水量大于、小于或等于蓝色水壶。假设这样的比较需要花费一个单位时间。 请找出一种算法,它能够用最少的比较次数来确定所有水壶的配对。 注意:不可直接比较两个红色或者两个蓝色水壶,一次比较必须取一只红色一只蓝色。
李振
2021/11/26
2680
快速排序 : 调优:3亿数据40秒,2亿数据30秒,1亿数据15秒
上一章我们讲到并归排序,并归排序的重要思想是对大问题进行分解,解决分解出来的小问题达到解决大问题的效果
执生
2020/09/27
5250
推荐阅读
相关推荐
一道朴实无华的算法题:把数组排成最小的数
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验