Go&java算法之最大数示例详解

目录
  • 最大数
  • 方法一:排序(java)
  • 方法一:排序(go)

最大数

给定一组非负整数 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 &lt; n; i++) {
            numsArr[i] = nums[i];
        }
        Arrays.sort(numsArr, (x, y) -&gt; {
            long sx = 10, sy = 10;
            while (sx &lt;= x) {
                sx *= 10;
            }
            while (sy &lt;= 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 &lt;= x {
            sx *= 10
        }
        for sy &lt;= y {
            sy *= 10
        }
        return sy*x+y &gt; 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)

以上就是Go&amp;java算法之最大数示例详解的详细内容,更多关于Go java算法最大数的资料请关注我们其它相关文章!

(0)

相关推荐

  • Go Java算法之交错字符串示例详解

    目录 交错字符串 方法一:动态规划(Java) 方法一:动态规划(GO) 交错字符串 给定三个字符串 s1.s2.s3,请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的. 两个字符串 s 和 t 交错 的定义与过程如下,其中每个字符串都会被分割成若干 非空 子字符串: s = s1 + s2 + ... + sn t = t1 + t2 + ... + tm |n - m| <= 1 交错 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 +

  • Go和Java算法详析之分数到小数

    目录 分数到小数 方法一:模拟竖式计算(Java) 方法一:模拟竖式计算(Go) 总结 分数到小数 给定两个整数,分别表示分数的分子 numerator 和分母 denominator,以 字符串形式返回小数 . 如果小数部分为循环小数,则将循环的部分括在括号内. 如果存在多个答案,只需返回 任意一个 . 对于所有给定的输入,保证 答案字符串的长度小于 104 . 示例 1: 输入:numerator = 1, denominator = 2 输出:"0.5" 示例 2: 输入:num

  • Go Java算法重复的DNA序列详解

    目录 重复的DNA序列 方法一:哈希表(Java) 方法二:哈希表——优化(Go) 方法思路: 重复的DNA序列 DNA序列 由一系列核苷酸组成,缩写为 'A', 'C', 'G' 和 'T'.. 例如,"ACGAATTCCG" 是一个 DNA序列 . 在研究 DNA 时,识别 DNA 中的重复序列非常有用. 给定一个表示 DNA序列 的字符串 s ,返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串).你可以按 任意顺序 返回答案. 示例 1: 输入:s = &

  • Go Java算法之比较版本号方法详解

    目录 比较版本号 方法一:字符串切割(Java) 方法二:双指针(Go) 比较版本号 给你两个版本号 version1 和 version2 ,请你比较它们. 版本号由一个或多个修订号组成,各修订号由一个 '.' 连接.每个修订号由 多位数字 组成,可能包含 前导零 .每个版本号至少包含一个字符. 修订号从左到右编号,下标从 0 开始,最左边的修订号下标为 0 ,下一个修订号下标为 1 ,以此类推.例如,2.5.33 和 0.1 都是有效的版本号. 比较版本号时,请按从左到右的顺序依次比较它们的

  • Go Java算法之外观数列实现方法示例详解

    目录 外观数列 方法一:遍历生成(Java) 方法二:递归(Go) 外观数列 给定一个正整数 n ,输出外观数列的第 n 项. 「外观数列」是一个整数序列,从数字 1 开始,序列中的每一项都是对前一项的描述. 你可以将其视作是由递归公式定义的数字字符串序列: countAndSay(1) = "1" countAndSay(n) 是对 countAndSay(n-1) 的描述,然后转换成另一个数字字符串. 前五项如下: 1.1 —— 第一项是数字 1 2.11 —— 描述前一项,这个数

  • Go Java算法之从英文中重建数字示例详解

    目录 从英文中重建数字 Java实现 Go实现 从英文中重建数字 给你一个字符串 s ,其中包含字母顺序打乱的用英文单词表示的若干数字(0-9).按 升序 返回原始的数字. 示例 1: 输入:s = "owoztneoer" 输出:"012" 示例 2: 输入:s = "fviefuro" 输出:"45" 提示: 1 <= s.length <= 105 s[i] 为 ["e","g&

  • Go&java算法之最大数示例详解

    目录 最大数 方法一:排序(java) 方法一:排序(go) 最大数 给定一组非负整数 nums,重新排列每个数的顺序(每个数不可拆分)使之组成一个最大的整数. 注意:输出结果可能非常大,所以你需要返回一个字符串而不是整数. 示例 1: 输入:nums = [10,2] 输出:"210" 示例 2: 输入:nums = [3,30,34,5,9] 输出:"9534330" 提示: 1 <= nums.length <= 100 0 <= nums[

  • java数据结构算法稀疏数组示例详解

    目录 一.什么是稀疏数组 二.场景用法 1.二维数组转稀疏数组思路 2.稀疏数组转二维数组思路 3.代码实现 一.什么是稀疏数组 当一个数组a中大部分元素为0,或者为同一个值,那么可以用稀疏数组b来保存数组a. 首先,稀疏数组是一个数组,然后以一种特定的方式来保存上述的数组a,具体处理方法: 记录数组a一共有几行几列 记录a中有多少个不同的值 最后记录不同值的元素所在行列,以及具体的值,放在一个小规模的数组里,以缩小程序的规模. 这个小规模的数组,就是稀疏数组. 举个栗子,左侧是一个二维数组,一

  • Java实现无向图的示例详解

    目录 基本概念 图的定义 无向图的定义 无向图的 API 无向图的实现方式 邻接矩阵 边的数组 邻接表数组 无向图的遍历 深度优先搜索 广度优先搜索 后记 基本概念 图的定义 一个图是由点集V={vi} 和 VV 中元素的无序对的一个集合E={ek} 所构成的二元组,记为G=(V,E),V中的元素vi叫做顶点,E中的元素 ek叫做边. 对于V中的两个点 u,v,如果边(u,v) 属于E,则称 u,v两点相邻,u,v称为边(u,v)的端点. 我们可以用m(G)=|E| 表示图G中的边数,用n(G)

  • java 算法之冒泡排序实例详解

    java 算法之冒泡排序实例详解 无人不知无人不晓的冒泡排序,据说是模仿泡泡从水中浮起跑到水面的过程. 在要排序的一组数中,对当前还未排好序的范围内的全部数,自上而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较小的往上冒.即: 每当两相邻的数比较后发现它们的排序与排序要求相反时,就将它们互换. 来看一下代码: package cn.songxinqiang.study.algorithm.sort; import java.util.Arrays; /** * 冒泡排序 * * <p>

  • Java反射框架Reflections示例详解

    MAVEN 坐标 <dependency> <groupId>org.reflections</groupId> <artifactId>reflections</artifactId> <version>0.9.10</version> </dependency> Reflections 的作用 Reflections通过扫描classpath,索引元数据,并且允许在运行时查询这些元数据. 获取某个类型的所有

  • C语言编程题杨氏矩阵算法快速上手示例详解

    目录 题目概要 一.解题思路 二.具体代码 题目概要 有一个数字矩阵,矩阵的每行从左到右都是递增的,矩阵从上到下都是递增的,请编写程序在这样的矩阵中查找某个数字是否存在? 一.解题思路 对于查找一个数组中元素是否存在,很多同学第一想法就是从头到尾遍历一遍.这样的想法优点是代码简单且无脑容易上手,但是这样的缺点也很明显,比如是m *n的数组,你从头到尾遍历,最坏情况要找m *n次.题目给的相关条件比如从左向右递增,从上向下递增你也完全没有使用,这样的暴力求解显然不是我们想看到的 我们来介绍一种方法

  • Java设计模式之单例模式示例详解

    目录 0.概述 1.饿汉式 1.1 饿汉式单例实现 1.2 破坏单例的几种情况 1.3 预防单例的破坏 2.枚举饿汉式 2.1 枚举单例实现 2.2 破坏单例 3.懒汉式 4.双检锁懒汉式 5.内部类懒汉式 6.JDK中单例的体现 0.概述 为什么要使用单例模式? 在我们的系统中,有一些对象其实我们只需要一个,比如说:线程池.缓存.对话框.注册表.日志对象.充当打印机.显卡等设备驱动程序的对象.事实上,这一类对象只能有一个实例,如果制造出多个实例就可能会导致一些问题的产生,比如:程序的行为异常.

  • java基础之注解示例详解

    目录 定义 作用 注解与注释的区别 JDK内置的标准注解 自定义注解 @Target 属性 定义 注解也叫原数据,它是JDK1.5及之后版本引入的一个特性,它可以声明在类.方法.变量等前面,用来对这些元素进行说明. 作用 生成文档:通过代码里标识的注解生成doc文档[生成doc文档] 代码分析:通过代码里标识的注解对代码进行分析[反射] 编译检查:通过代码里标识的注解让编译器能够实现基本的编译检查[Override] 注解与注释的区别 注解是给编译器看的,注释是给程序员看的. JDK内置的标准注

  • Java代理模式的示例详解

    目录 定义 案例 需求 方案:静态代理模式 总结 定义 代理模式(Proxy Parttern) 为一个对象提供一个替身,来控制这个对象的访问,即通过代理对象来访问目标对象,这样做的话好处是可以在目标对象实现的基础上,进行额外的功能的扩展. 案例 需求 苹果公司通过苹果代理商来卖手机 方案:静态代理模式 定义抽象接口类,该类在代理模式中扮演的是一个抽象功能的角色,该案例中就是把出售手机抽象为了一个接口 /** * 售卖手机的接口(代理模式--抽象角色) * @author:liyajie * @

  • Java动态代理的示例详解

    目录 定义 分类 案例 需求 方案一:jdk动态代理 方案二:cglib动态代理 分析 总结 定义 动态代理指的是,代理类和目标类的关系在程序运行的时候确定的,客户通过代理类来调用目标对象的方法,是在程序运行时根据需要动态的创建目标类的代理对象. 分类 jdk动态代理 cglib动态代理 案例 需求 苹果公司通过苹果代理商来卖手机 方案一:jdk动态代理 定义抽象接口 /** * 售卖手机的接口(代理模式--抽象角色) * @author:liyajie * @createTime:2022/2

随机推荐