leetcode-179-Largest Number(理解规则,自定义cmp函数进行排序)

题目描述:

给定一组非负整数,重新排列它们的顺序使之组成一个最大的整数。

示例 1:

输入: [10,2]
输出: 210

示例 2:

输入: [3,30,34,5,9]
输出: 9534330

说明: 输出结果可能非常大,所以你需要返回一个字符串而不是整数。

要完成的函数:

string largestNumber(vector<int>& nums) 

说明:

1、这道题给定一个vector,里面存放着int类型的非负整数,要求把这些非负整数拼起来,尽可能拼成一个最大的整数。

比如[10,2],可以拼成102,也可以拼成210,最大的整数就是210,那么返回210,以字符串的形式。

2、这道题关键在于判断,判断vector中的两个数谁大谁小,谁应该放在前面。

举个例子,比如[3,30,31,32,33,34,35,102,9,990],大家觉得应该怎么排序?

我们要尽可能让大的数字放在前面,所以首位肯定要放个大一点的,那么就是9了,其余的都是3,放在首位不合适。

那么9有两个,要放9还是990,这里要对这两个数的组合做个判断。

一种是9990,一种是9909,所以还是9-990这种组合。

那么接下来呢,9-990之后呢?3跟30比,一种是330,一种是303,所以还是3在30前面。

那3跟31比呢,一种是331,一种是313,还是3在31前面。

是不是所有短的数字都要放在前面?

其实不是的,比如3和34,一种是334,一种是343,还要考虑到后面这一位的情况。

所以最终排列下来,“降序”排列,是[9,990,35,34,33,3,32,31,30]。

按照这个vector从前往后添加到要返回的字符串中,就可以了。

这道题的关键在于判断谁在前谁在后,比较的方法也很普通,就是补齐两个字符串,比较谁大谁小。

当然在实际操作中,没有必要真的对字符串补齐,我们同样可以操作。

代码如下:(附详解)

    static bool cmp(int &a1,int &b1)//自定义一个比较函数,大的放前面
    {
    	string a=to_string(a1),b=to_string(b1);//先把两个整数转化为字符串,操作起来比较方便
        int s1=a.size(),s2=b.size();
        if(s1<s2)//如果a短b长
        {
            for(int i=0;i<s1;i++)//在a的长度内比较
            {
                if(a[i]>b[i])//如果发现a中的某一位数值已经大于b中同一位的数值,比如4和39
                    return true;//那么比较到此结束,4要放在前面
                else if(a[i]<b[i])//如果发现a中的某一位数值已经小于b中同一位的数值,比如4和61
                    return false;//那么比较到此结束,61要放在前面
            }
            for(int i=s1;i<s2;i++)//如果上面的比较没出结果,比如4和456这种情况,那么开始新的比较,直到到达第二个字符串的最后一位
            {            //这个循环其实比较的是4和5,5和6,到达第二个字符串的最后一位就不比较了
                if(b[i-s1]>b[i])//如果满足条件,那么a要放在前面
                    return true;
                else if(b[i-s1]<b[i])//如果满足条件,那么b要放在前面
                    return false;
            }
            for(int i=0;i<s1;i++)//如果上面的比较没出结果,其实我们还有最后一位没有比较,6和4
            {
            	if(a[i]<b[s2-s1+i])
            		return true;
            	else if(a[i]>b[s2-s1+i])
            		return false;
			}
            return false;//如果上述比较都没出结果,比如3和333,那么返回false,这里随便拼都可以
        }
        else if(s1>s2)//如果a长b短,一样的比较方式
        {
            for(int i=0;i<s2;i++)
            {
                if(a[i]<b[i])
                    return false;
                else if(a[i]>b[i])
                    return true;
            }
            for(int i=s2;i<s1;i++)
            {
                if(a[i-s2]>a[i])
                    return false;
                else if(a[i-s2]<a[i])
                    return true;
            }
            for(int i=0;i<s2;i++)
            {
            	if(b[i]>a[s1-s2+i])
            		return true;
            	else if(b[i]<a[s1-s2+i])
            		return false;
			}
            return false;
        }
        else//如果两个一样长,那么直接逐位比较就可以了
        {
            for(int i=0;i<s1;i++)
            {
                if(a[i]>b[i])
                    return true;
                else if(a[i]<b[i])
                    return false;
            }
            return false;
        }
    }
    string largestNumber(vector<int>& nums) 
    {
        sort(nums.begin(),nums.end(),cmp);//调用sort函数进行排序,排序准则是我们自定义的比较函数
        string res;
        for(auto i:nums)
            res+=to_string(i);//不断地插入到字符串的末尾
        if(res[0]=='0')return "0";//边界条件,如果第一位是0,那么说明后面即使有,也是全0,这时候我们只需要返回0就可以了了,而不是一长串的0
        return res;
    }

上述代码实测4ms,beats 99.85% of cpp submissions。

关于cmp函数,笔者在网上看到过一个简单的降序排列的版本,如下:

    bool cmp1(int &a,int &b)
    {
    	return a>b;
	}
    int main()
	{
		vector<int>nums={1,2,3,4,5,6,7,8,9,10,11,12};
		sort(nums.begin(),nums.end(),cmp1);
		for(int i:nums)
		cout<<i<<"  ";
		cout<<endl;
		return 0;
	} 

上面的cmp1这个函数,笔者个人猜想其实是说,如果a>b,那么返回true,认为前面的数大于后面的数是正确的。

所以在进行排序的时候,如果前面的数大于后面的,那么经过cmp1这个函数,返回true,认为正确,所以不用更改。

如果前面的数小于后面的数,那么经过cmp1这个函数,返回false,认为错误,所以要换一下位置。

所以笔者就根据自己的猜想,设计了题解代码中的cmp函数,从结果来看,上述认识还是有一定可取之处的。

但上述仅为笔者个人的猜想,有可能是不完全的甚至有些错误,没有仔细地去查sort函数的参数,仅作为一个个人的认识。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏用户2442861的专栏

JavaScript 正则表达式上——基本语法

JavaScript种正则表达式有两种定义方式,定义一个匹配类似 <%XXX%> 的字符串

671
来自专栏web前端教室

不学不知道,sort()方法中的坑

今天的前端零基础课,在讲到js中的sort()排序方法的时候,说sort()这个方法在给数字排序的时候,根本不是按数字大小来排序的。 它是把数字都当成字符串来看...

19010
来自专栏前端小栈

正则详解

转自: JS正则表达式一条龙讲解,从原理和语法到JS正则、ES6正则扩展,最后再到正则实践思路

1163
来自专栏趣谈编程

Unicode与UTF-8的区别

要弄清Unicode与UTF-8的关系,我们还得从他们的来源说起,下来我们从刚开始的编码说起,直到Unicode的出现,我们就会感觉到他们之间的关系

1282
来自专栏大数据学习笔记

Java程序设计(Java9版):第2章 数据类型与运算符(Data types and Operators)

第2章 数据类型与运算符(Data types and Operators) I think everybody in this country should ...

2555
来自专栏函数式编程语言及工具

Scalaz(12)- Monad:再述述flatMap,顺便了解MonadPlus

  在前面的几篇讨论里我们初步对FP有了些少了解:FP嘛,不就是F[A]吗?也是,FP就是在F[]壳子(context)内对程序的状态进行更改,也就是在F壳子(...

1957
来自专栏前端吧啦吧啦

涨薪必备Javascript,快点放进小口袋!

1402
来自专栏黑泽君的专栏

java基础学习_基础语法(上)01_day02总结

=============================================================================

1153
来自专栏mathor

ST算法

 RMQ(Range Minimum/Maximum Query),即区间最值查询。对于长度为n的数列arr,回答若干询问Q(i,j),返回数列arr中下标在i...

2172
来自专栏CDA数据分析师

算法和数据结构—— 查找和排序

本文为简书作者郑永欣原创,CDA数据分析师已获得授权 查找和排序都是程序设计中经常用到的算法。查找相对而言较为简单,不外乎顺序查找、二分查找、哈希表查找和二叉排...

2406

扫码关注云+社区

领取腾讯云代金券