剑指Offer(三十二):把数组排成最小的数

2018年1月6日12:49:31 4 771 °C
摘要

输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。

剑指Offer(三十二):把数组排成最小的数

一、前言

本系列文章为《剑指Offer》刷题笔记。

刷题平台:牛客网

书籍下载:共享资源

二、题目

输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。

1、思路

遇到这个题,全排列当然可以做,但是时间复杂度为O(n!)。在这里我们自己定义一个规则,对拼接后的字符串进行比较。

排序规则如下:

  • 若ab > ba 则 a 大于 b,
  • 若ab < ba 则 a 小于 b,
  • 若ab = ba 则 a 等于 b;

根据上述规则,我们需要先将数字转换成字符串再进行比较,因为需要串起来进行比较。比较完之后,按顺序输出即可。

2、代码

C++:

Python:

注意在C++中,cmp函数要是使用static进行声明,声明是静态成员函数,这样才能正确调用。

weinxin
微信公众号
分享技术,乐享生活:Jack Cui公众号每周五推送“程序员欢乐送”系列资讯类文章,欢迎您的关注!
Jack Cui

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

目前评论:4   其中:访客  2   博主  2

    • avatar 裸奔的麻瓜 来自天朝的朋友 谷歌浏览器  LLD-AL10 Build/HONORLLD-AL10 广东省深圳市罗湖区 电信 2

      大神,C++第8行,调用cmp是否少了参数

        • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Windows 7 辽宁省沈阳市 东北大学三舍南(研究生)

          @裸奔的麻瓜 没有,看下sort的用法你就知道了。

        • avatar 裸奔的麻瓜 来自天朝的朋友 谷歌浏览器  LLD-AL10 Build/HONORLLD-AL10 广东省深圳市罗湖区 电信 2

          谢谢指点,另外问一下,python第7 行cmp好像没有定义呢?

            • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器  Android 8.0.0 MIX 2 Build/OPR1.170623.027 辽宁省沈阳市 联通GSM/WCDMA/LTE共用出口

              @裸奔的麻瓜 这是python内置函数。