文档章节

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

孟飞阳
 孟飞阳
发布于 2017/07/23 21:06
字数 286
阅读 9
收藏 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]

 

© 著作权归作者所有

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

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

小帅帅丶
2015/01/09
0
7
可视化的数据结构和算法

还记得之前发布过的那个关于可视化排序的文章吗?在网上又看到了一个旧金山大学David Galles做的各种可视化的数据结构和基本算法的主页,网址在这里,大家可以看看。我把这个页面的目录列在下...

戴威
2011/05/12
962
5
05《Java核心技术》之三种字符串类有什么区别?

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

飞鱼说编程
2018/09/24
0
0
JAVA 持有对象——容器初探

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

jiangmitiao
2015/08/01
0
2
可视化的数据结构和算法

还记得之前发布过的那个关于可视化排序的文章吗?在网上又看到了一个旧金山大学David Galles做的各种可视化的数据结构和基本算法的主页,网址在这里,大家可以看看。我把这个页面的目录列在下...

戴威
2011/05/12
16
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周二乱弹 —— 以后我偷小鱼干养你

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @庞巴哥 :只有这节奏瞬间变得轻松。。。。。。。。。分享Talking Eyes的单曲《In the sun (Extended Version)》: 《In the sun (Extended Ve...

小小编辑
59分钟前
2
0
多表查询

第1章 多表关系实战 1.1 实战1:省和市  方案1:多张表,一对多  方案2:一张表,自关联一对多 1.2 实战2:用户和角色 (比如演员和扮演人物)  多对多关系 1.3 实战3:角色和权限 (比如...

stars永恒
今天
7
0
求推广,德邦快递坑人!!!!

完全没想好怎么来吐槽自己这次苦逼的德邦物流过程了,只好来记一个流水账。 从寄快递开始: 2019年1月15日从 德邦物流 微信小app上下单,截图如下: 可笑的是什么,我预约的是17号上门收件,...

o0无忧亦无怖
昨天
10
0
Mac Vim配置

1.升级 vim   我自己 MacBook Pro 的系统还是 10.11 ,其自带的 vim 版本为 7.3 ,我们将其升至最新版: 使用 homebrew : brew install vim --with-lua --with-override-system-vim 这将下...

Pasenger
昨天
9
0
vmware安装Ubuntu上不了网?上网了安装不了net-tools,无法执行ifconfig?

1.重新设置网络适配器还是不行,如下指定nat 2.还需要指定共享网络,我是在无线环境下 3.无法执行ifconfig https://packages.ubuntu.com/bionic/net-tools到这个网站下载net-tools的deb文件...

noob_chr
昨天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部