379.Reorder array to construct the minimum number-将数组重新排序以构造最小值(中等题)

本文主要是介绍379.Reorder array to construct the minimum number-将数组重新排序以构造最小值(中等题),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

将数组重新排序以构造最小值

  1. 题目

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

  2. 样例

    给定 [3, 32, 321],通过将数组重新排序,可构造 6 个可能性数字:
    3+32+321=332321
    3+321+32=332132
    32+3+321=323321
    32+321+3=323213
    321+3+32=321332
    321+32+3=321323
    其中,最小值为 321323,所以,将数组重新排序后,该数组变为 [321, 32, 3]。

  3. 挑战

    在原数组上完成,不使用额外空间。

  4. 题解

    本题类似于184.Largest Number-最大数(中等题),是求最小数。但是由于题目要求不能使用额外空间,则需要我们自己实现排序算法(这里使用的是快排算法),元素大小比较可参见184题。

public class Solution {/*** @param nums n non-negative integer array* @return a string*/public String minNumber(int[] nums) {StringBuilder sb = new StringBuilder();quickSort(nums,0,nums.length-1);for (int i=0;i<nums.length;i++){if (sb.length() == 0 && nums[i] == 0){continue;}sb.append(String.valueOf(nums[i]));}return sb.length() == 0 ? "0" : sb.toString();}private int compare(int o1, int o2){return (String.valueOf(o1)+String.valueOf(o2)).compareTo(String.valueOf(o2)+String.valueOf(o1));}private void quickSort(int[] a, int left, int right){if (left < right){int temp = a[left];int i = left;int j = right;while (i < j){while (j > i && compare(a[j],temp) >=0){j--;}while (i < j && compare(a[i],temp) <= 0){i++;}if (i < j){swap(a, i, j);}}swap(a, left, j);quickSort(a,left,i-1);quickSort(a, i+1, right);}}private void swap(int[] a, int i, int j){int temp = a[j];a[j] = a[i];a[i] = temp;}
}

Last Update 2016.11.11

这篇关于379.Reorder array to construct the minimum number-将数组重新排序以构造最小值(中等题)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/925865

相关文章

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案(推荐)2. 模糊匹配方案参数化查询示例使用场景建议性能优

关于集合与数组转换实现方法

《关于集合与数组转换实现方法》:本文主要介绍关于集合与数组转换实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、Arrays.asList()1.1、方法作用1.2、内部实现1.3、修改元素的影响1.4、注意事项2、list.toArray()2.1、方

MySQL 中 ROW_NUMBER() 函数最佳实践

《MySQL中ROW_NUMBER()函数最佳实践》MySQL中ROW_NUMBER()函数,作为窗口函数为每行分配唯一连续序号,区别于RANK()和DENSE_RANK(),特别适合分页、去重... 目录mysql 中 ROW_NUMBER() 函数详解一、基础语法二、核心特点三、典型应用场景1. 数据分

一文详解Java Stream的sorted自定义排序

《一文详解JavaStream的sorted自定义排序》Javastream中的sorted方法是用于对流中的元素进行排序的方法,它可以接受一个comparator参数,用于指定排序规则,sorte... 目录一、sorted 操作的基础原理二、自定义排序的实现方式1. Comparator 接口的 Lam

CSS Anchor Positioning重新定义锚点定位的时代来临(最新推荐)

《CSSAnchorPositioning重新定义锚点定位的时代来临(最新推荐)》CSSAnchorPositioning是一项仍在草案中的新特性,由Chrome125开始提供原生支持需... 目录 css Anchor Positioning:重新定义「锚定定位」的时代来了! 什么是 Anchor Pos

MySQL JSON 查询中的对象与数组技巧及查询示例

《MySQLJSON查询中的对象与数组技巧及查询示例》MySQL中JSON对象和JSON数组查询的详细介绍及带有WHERE条件的查询示例,本文给大家介绍的非常详细,mysqljson查询示例相关知... 目录jsON 对象查询1. JSON_CONTAINS2. JSON_EXTRACT3. JSON_TA

Java List排序实例代码详解

《JavaList排序实例代码详解》:本文主要介绍JavaList排序的相关资料,Java排序方法包括自然排序、自定义排序、Lambda简化及多条件排序,实现灵活且代码简洁,文中通过代码介绍的... 目录一、自然排序二、自定义排序规则三、使用 Lambda 表达式简化 Comparator四、多条件排序五、

JAVA数组中五种常见排序方法整理汇总

《JAVA数组中五种常见排序方法整理汇总》本文给大家分享五种常用的Java数组排序方法整理,每种方法结合示例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录前言:法一:Arrays.sort()法二:冒泡排序法三:选择排序法四:反转排序法五:直接插入排序前言:几种常用的Java数组排序

重新对Java的类加载器的学习方式

《重新对Java的类加载器的学习方式》:本文主要介绍重新对Java的类加载器的学习方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、介绍1.1、简介1.2、符号引用和直接引用1、符号引用2、直接引用3、符号转直接的过程2、加载流程3、类加载的分类3.1、显示

Java数组初始化的五种方式

《Java数组初始化的五种方式》数组是Java中最基础且常用的数据结构之一,其初始化方式多样且各具特点,本文详细讲解Java数组初始化的五种方式,分析其适用场景、优劣势对比及注意事项,帮助避免常见陷阱... 目录1. 静态初始化:简洁但固定代码示例核心特点适用场景注意事项2. 动态初始化:灵活但需手动管理代