文档章节

Java实现正整数数组的最小拼接数

孟飞阳
 孟飞阳
发布于 2017/07/23 21:06
字数 286
阅读 7
收藏 0

题目:输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字321323.

tip:你能在多长时间解决呢?请快速给出思路!

源码:

package demo1;

import java.util.Arrays;

public class IntArrayMax {
	public static void main(String args[]) {

		int[] num = { 1, 5, 9, 13, 442, 44, 6, 21, 211 };
		IntArrayMax arra = new IntArrayMax();
		arra.qsort(num, 0, num.length - 1);

		System.out.println(Arrays.toString(num));
	}

	public void qsort(int[] num, int left, int right) {
		if (left < right) {
			int partition = partition(num, left, right);
			qsort(num, left, partition - 1);
			qsort(num, partition + 1, right);
		}
	}

	public int partition(int[] num, int left, int right) {
		int partition = num[left];
		while (left < right) {
			while ((num[right] == partition || isMBigerThanN(num, num[right],
					partition)) && left < right) {
				right--;
			}
			swap(num, left, right);
			while ((num[left] == partition || isMBigerThanN(num, partition,
					num[left])) && left < right) {
				left++;
			}
			swap(num, left, right);
		}
		return left;
	}

	public void swap(int[] num, int m, int n) {
		int temp = num[m];
		num[m] = num[n];
		num[n] = temp;
	}

	public boolean isMBigerThanN(int[] num, int m, int n) {
		String num1 = String.valueOf(m);
		String num2 = String.valueOf(n);
		int temp1 = Integer.parseInt(num1 + num2);
		int temp2 = Integer.parseInt(num2 + num1);
		if (temp1 > temp2) {
			return true;
		}
		else {
			return false;
		}
	}
}

输出:

[1, 13, 211, 21, 442, 44, 5, 6, 9]

 

© 著作权归作者所有

共有 人打赏支持
孟飞阳
粉丝 206
博文 971
码字总数 544356
作品 5
朝阳
个人站长
私信 提问
程序员必知的8大排序(java实现)

8种排序之间的关系:  1、 直接插入排序   (1)基本思想:   在要排序的一组数中,假设前面(n-1)[n>=2] 个数已经是排好顺序的,现在要把第n个数插到前面的有序数中,使得这n个数也是排好...

小帅帅丶
2015/01/09
0
7
JAVA 持有对象——容器初探

引言 如果一个程序只包含固定数量的且其生命周期都是已知对象,那么这是一个非常简单的程序——《think in java》 了解容器前,先提出一个问题,ArrayList和LinkedList谁的处理速度更快呢? ...

jiangmitiao
2015/08/01
0
2
05《Java核心技术》之三种字符串类有什么区别?

一、提出问题 今天,我们来聊聊日常使用的字符串,别看它似乎很简单,但其实字符串几乎在所有编程语言里都是个特殊的存在,因为不管是数量还是体积,字符串都是大多数应用中的重要组成。 今天...

飞鱼说编程
09/24
0
0
Comparator与Comparable的应用

当需要排序的集合或数组不是单纯的数字型时,通常可以使用Comparator或Comparable,以简单的方式实现对象排序或自定义排序。 阅读过程中有任何问题,请联系egg: 邮箱:xtfggef@gmail.com 微...

mrliuze
2015/08/04
0
0
561. Array Partition I - LeetCode

Question 561. Array Partition I Solution 题目大意是,给的数组大小是2n,把数组分成n组,每组2个元素,每个组取最小值,这样就能得到n个值,怎样分组才能使这n个数相加最小。 思路:有点田...

yysue
06/30
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Apache日志不记录访问静态文件,访问日志切割,静态元素过期时间设置

Apache配置不记录访问静态文件的日志 网站大多元素为静态文件,如图片、css、js等,这些元素可以不用记录 vhost原始配置 <VirtualHost *:80> ServerAdmin test@163.com DocumentRoo...

野雪球
37分钟前
0
0
聊聊storm的ICommitterTridentSpout

序 本文主要研究一下storm的ICommitterTridentSpout ICommitterTridentSpout storm-core-1.2.2-sources.jar!/org/apache/storm/trident/spout/ICommitterTridentSpout.java public interface......

go4it
41分钟前
1
0
Ubuntu常用操作

查看端口号 netstat -anp |grep 端口号 查看已使用端口情况 netstat -nultp(此处不用加端口号) netstat -anp |grep 82查看82端口的使用情况 查找被占用的端口: netstat -tln netstat -tl...

hc321
昨天
1
0
网站cdn的静态资源突然访问变的缓慢,问题排查流程

1.首先我查看了一下是否自己的网络问题,通过对比其他资源的访问速度和下载速度,确认不是 2.通过ping 和 tracert 判断cdn域名能否正常访问,(最后回想感觉这一步可以省略,因为每次最终能访...

小海bug
昨天
3
0
Mybatis 学习笔记四 MyBatis-Plus插件

Mybatis 学习笔记四 MyBatis-Plus插件 maven依赖 <dependency> <groupId>com.baomidou</groupId> <artifactId>mybatis-plus</artifactId> <ve......

晨猫
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部