Go&java算法之最大数示例详解
作者:黄丫丫 发布时间:2023-10-30 08:54:56
标签:Go,java,算法,最大数
最大数
给定一组非负整数 nums,重新排列每个数的顺序(每个数不可拆分)使之组成一个最大的整数。
注意:输出结果可能非常大,所以你需要返回一个字符串而不是整数。
示例 1:
输入:nums = [10,2]
输出:"210"
示例 2:
输入:nums = [3,30,34,5,9]
输出:"9534330"
提示:
1 <= nums.length <= 100
0 <= nums[i] <= 109
方法一:排序(java)
要想组成最大的整数,一种直观的想法是把数值大的数放在高位。
于是我们可以比较输入数组的每个元素的最高位,最高位相同的时候比较次高位
以此类推,完成排序,然后把它们拼接起来。这种排序方式对于输入数组 没有相同数字开头 的时候是有效的
class Solution {
public String largestNumber(int[] nums) {
int n = nums.length;
// 转换成包装类型,以便传入 Comparator 对象(此处为 lambda 表达式)
Integer[] numsArr = new Integer[n];
for (int i = 0; i < n; i++) {
numsArr[i] = nums[i];
}
Arrays.sort(numsArr, (x, y) -> {
long sx = 10, sy = 10;
while (sx <= x) {
sx *= 10;
}
while (sy <= y) {
sy *= 10;
}
return (int) (-sy * x - y + sx * y + x);
});
if (numsArr[0] == 0) {
return "0";
}
StringBuilder ret = new StringBuilder();
for (int num : numsArr) {
ret.append(num);
}
return ret.toString();
}
}
时间复杂度:O(nlognlogm)
空间复杂度:O(logn)
方法一:排序(go)
具体的方法思路已经在上文中表述,详情请看上文内容。
1.核心为插入排序
2.比大小的函数,相加的两种string结果,然后比较各位大小。
3.将排序的结果累加
func largestNumber(nums []int) string {
sort.Slice(nums, func(i, j int) bool {
x, y := nums[i], nums[j]
sx, sy := 10, 10
for sx <= x {
sx *= 10
}
for sy <= y {
sy *= 10
}
return sy*x+y > sx*y+x
})
if nums[0] == 0 {
return "0"
}
ans := []byte{}
for _, x := range nums {
ans = append(ans, strconv.Itoa(x)...)
}
return string(ans)
}
时间复杂度:O(nlognlogm)
空间复杂度:O(logn)
来源:https://juejin.cn/post/7131371861677932552
0
投稿
猜你喜欢
- 多播委托简介每一个委托都是继承自MulticastDelegate,也就是每个都是多播委托。带返回值的多播委托只返回最后一个方法的值多播委托
- 一、什么是过滤器过滤器是对数据进行过滤,预处理过程,当我们访问网站时,有时候会发布一些敏感信息,发完以后有的会用*替代,还有就是登陆权限控制
- 方法的重写(Overriding)和重载(Overloading)是Java多态性的不同表现。重写(Overriding)是父类与子类之间多
- 本教程基于 JetBrains IntelliJ IDEA 2018.3.6 编写,高版本未经测试,或有不兼容,请见谅!JetBrains
- 定义:将一个请求封装成一个对象,从而让你使用不同的请求把客户端参数化,对请求排队或者记录请求日志,可以提供命令的撤销和恢复功能。类型:行为类
- 在没介绍正文之前,先给大家介绍下websocket的背景和原理:背景在浏览器中通过http仅能实现单向的通信,comet可以一定程度上模拟双
- 概述1、邮件相关的标准厂商所提供的 JavaMail 服务程序可以有选择地实现某些邮件协议,常见的邮件协议包括:SMTP(Simple Ma
- 无聊逛论坛,发现了这张图真是厉害啊,这排序, 既有多线程,又有排序,还有lambda表达式,但是这是C#版本,作为一个入坑的Java爱好者,
- Condition的作用是对锁进行更精确的控制。Condition中的await()方法相当于Object的wait()方法,Conditi
- 重复参数 Scala在定义函数时允许指定最后一个参数可以重复(变长参数),从而允许函数调用者使用变长参数列表来调用该函数,Scala中使用“
- 前言加密配置是一个很常见的需求,在spring boot生态中,已经有非常多的第三方starter实现了,博主所在公司也有这种强制要求,一些
- 一、return语句执行顺序finally语句是在return语句执行之后,return语句返回之前执行的package exception
- 一、新建BeanUtil类import lombok.extern.slf4j.Slf4j;import org.springframewo
- currentThread的详解currentThread方法是Thread类的一个静态方法,用来获取当前运行的代码段,正在被哪个线程调用。
- 本文实例讲述了java在网页上面抓取邮件地址的方法。分享给大家供大家参考。具体实现方法如下:import java.io.BufferedR
- java 算法之希尔排序一、思想 希尔排序:使数组中任意间隔为h的元素都是有序的。在进行排序的时候,如果h很大,我们就能将元素移动到很远的地
- 前言该篇介绍的内容如题,就是利用redis实现接口的限流( 某时间范围内 最大的访问次数 ) 。正文 惯例,
- 前言上一篇我们介绍了使用 sqflite 这个数据库工具在 Flutter 的应用中建立本地数据库的实例应用。了解过数据库的同学应该会知道,
- 这篇文章主要介绍了java 读取系统Properties代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值
- 1、线性表定义线性表是最基本、最简单、也是最常用的一种数据结构。线性表(linear list)是数据结构的一种,一个线性表是n个具有相同特