文档章节

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

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

 

孟飞阳

孟飞阳

粉丝 224
博文 1075
码字总数 572007
作品 5
朝阳
个人站长
私信 提问
加载中
请先登录后再评论。
Netty那点事(三)Channel与Pipeline

Channel是理解和使用Netty的核心。Channel的涉及内容较多,这里我使用由浅入深的介绍方法。在这篇文章中,我们主要介绍Channel部分中Pipeline实现机制。为了避免枯燥,借用一下《盗梦空间》的...

黄亿华
2013/11/24
2W
22
用vertx实现高吞吐量的站点计数器

工具:vertx,redis,mongodb,log4j 源代码地址:https://github.com/jianglibo/visitrank 先看架构图: 如果你不熟悉vertx,请先google一下。我这里将vertx当作一个容器,上面所有的圆圈要...

jianglibo
2014/04/03
4.1K
3
SQLServer实现split分割字符串到列

网上已有人实现sqlserver的split函数可将字符串分割成行,但是我们习惯了split返回数组或者列表,因此这里对其做一些改动,最终实现也许不尽如意,但是也能解决一些问题。 先贴上某大牛写的s...

cwalet
2014/05/21
9.6K
0
【opencv】图形的绘制

1.矩形图像的绘制: 原函数:void cvRectangle(CvArr* img, CvPoint pt1, CvPoint pt2, CvScalar color, int thickness=1, int line_type=8,int shift=0) img就是需要绘制的图像 pt1 and pt......

其实我是兔子
2014/10/08
1.2K
1
Swift百万线程攻破单例(Singleton)模式

一、不安全的单例实现 在上一篇文章我们给出了单例的设计模式,直接给出了线程安全的实现方法。单例的实现有多种方法,如下面: class SwiftSingleton { } 这段代码的实现,在shared中进行条...

一叶博客
2014/06/20
3.4K
16

没有更多内容

加载失败,请刷新页面

加载更多

发布新版首页“外婆新家”升级版:全新的UI,熟悉的味道

在7月30日我们我们忐忑不安地发布了新版网站首页,发布后迎接我们的不是新颜新风貌的惊喜,而是我们最担心的残酷现实——“让我们等这么多年,等来的就是这个新的丑容颜”,在大家的批评声中...

osc_8grrbqh4
1分钟前
0
0
markLine 标示线的使用

markLine 可以单独写在一个对象里,也可以接在其它数据下面,如果将 markLine 单独写在一个对象里,就必须加 type ,不然报错。 markLine 的 data 和其它 data 一样,也可以单独设置样式。 ...

osc_z3aalppw
2分钟前
0
0
新的日记 ~

新开一个日记本,以后都用这个好啦(真的以后都用这个了……)。 放一下旧的日记: 日记 2018 下半年:https://www.cnblogs.com/nanjoqin/p/9885681.html 日记 2019 上半年:https://www.cnb...

osc_tj0is418
4分钟前
0
0
ROC与AUC曲线绘制

由于ROC曲线面积比较难求得,所以判断模型好坏一般使用AUC曲线 关于AUC曲线的绘制,西瓜书上写得比较学术,不太能理解,假设有这么一个样本集: 假设预测样本为20个,预测为正类的概率已经进...

osc_votswz18
5分钟前
0
0
IDEA 2020.2 稳定版发布,带来了不少新功能...

点击上方“朱小厮的博客”,选择“设为星标” 后台回复"书",获取 来源 | https://www.oschina.net/news/117535/intellij-idea-2020-2-released IntelliJ IDEA 2020.2 稳定版已发布,此版本带...

osc_hr0pxr5d
7分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部