文档章节

Lintcode379 Reorder array to construct the minimum number solution 题解

顾情笙
 顾情笙
发布于 2018/03/05 22:37
字数 299
阅读 30
收藏 0

【题目描述】

Construct minimum number by reordering a given non-negative integer array. Arrange them such that they form the minimum number.

Notice:The result may be very large, so you need to return a string instead of an integer.

给定一个整数数组,请将其重新排序,以构造最小值。

【注】:结果可能非常大,因此你需要返回一个字符串而不是一个整数。

【题目链接】

www.lintcode.com/en/problem/reorder-array-to-construct-the-minimum-number/

【题目解析】

这道题关键在于字符串两两之间的大小比较以及排序算法。

这里排序算法用Java底层用归并实现的Arrays.sort,能将排序的时间复杂度控制在O(n*lnon)。

对于字符串的两两比较,按照我们这道题的思路,我们需要比较的是两两字符串s1,s2拼接是s1拼s2还是s2拼s1大,根据这句话,我们就可以直接通过比较s1+s2和s2+s1的字符序大小来得到我们的结果。

因为是要求最小的数,所以可能0会出现在最后拼接成的字符串最前面,我们需要把前导0去掉。

【参考题解】

www.jiuzhang.com/solutions/reorder-array-to-construct-the-minimum-number/

© 著作权归作者所有

顾情笙
粉丝 0
博文 10
码字总数 3288
作品 0
成都
私信 提问
加载中

评论(0)

POJ 刷题系列:3274. Gold Balanced Lineup

POJ 刷题系列:3274. Gold Balanced Lineup 传送门:3274. Gold Balanced Lineup 题意: 官方题解: Consider the partial sum sequence of each of the k features built by taking the su......

Demon的黑与白
04/01
0
0
构造大根树 Maximum Binary Tree

问题: Given an integer array with no duplicates. A maximum tree building on this array is defined as follow: The root is the maximum number in the array. The left subtree is th......

叶枫啦啦
2018/01/13
21
0
Codeforces 960C - Subsequence Counting 【思维+构造】

C. Subsequence Counting time limit per test 1second memory limit per test 256megabytes Pikachu had an array with him. He wrotedown all the non-empty subsequences of the array on......

my_sunshine26
2018/04/08
0
0
决战Leetcode: easy part(1-50)

本博客是个人原创的针对leetcode上的problem的解法,所有solution都基本通过了leetcode的官方Judging,个别未通过的例外情况会在相应部分作特别说明。 欢迎互相交流! email: tomqianmaple@...

qq_32690999
2018/01/25
0
0
Codeforces Round #602 (Div. 2, based on Technocup 2020 Elimination Round 3) B. Box 贪心

B. Box Permutation p is a sequence of integers p=[p1,p2,…,pn], consisting of n distinct (unique) positive integers between 1 and n, inclusive. For example, the following sequen......

qscqesze
2019/11/24
0
0

没有更多内容

加载失败,请刷新页面

加载更多

情感分析

本文作者:在线实验室 文章结构: 背景介绍——模型概览——数据集介绍——配置模型——训练模型——应用模型——应用模型并进行预测——总结——参考文献 本教程源代码目录在book/understa...

百度开发者中心
2019/03/30
21
0
008. 并发容器类 Map

1. JDK 源码学习方法 1. 演绎推导法 示例:因果推理。 因为 JAVA 中只提供了 BIO 和 NIO 两种方式,所以一切框架中,涉及到网络处理的,都可以用这两个知识点去探究原理。 2. 归纳总结法 示例...

紫穹
16分钟前
10
0
如何使用sed替换换行符(\\ n)? - How can I replace a newline (\n) using sed?

问题: How can I replace a newline (" \\n ") with a space (" 如何将换行符(“ \\n ”)替换为空格(“ ") using the sed command? “)使用sed命令? I unsuccessfully tried: 我尝试失......

javail
22分钟前
20
0
OSChina 周一乱弹 —— 原来这叫分别焦虑

Osc乱弹歌单(2020)请戳(这里) 【今日歌曲】 @薛定谔的兄弟 :分享洛神有语创建的歌单「我喜欢的音乐」: 《A Careful Tearing》- Levi Patel 手机党少年们想听歌,请使劲儿戳(这里) 清明...

小小编辑
今天
114
0
trim、stripslashes、htmlspecialchars函数

通过 PHP 验证表单数据 我们要做的第一件事是通过 PHP 的 htmlspecialchars() 函数传递所有变量。 在我们使用 htmlspecialchars() 函数后,如果用户试图在文本字段中提交以下内容: <script>...

imzchloe
今天
97
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部