Java实现正整数数组的最小拼接数
Java实现正整数数组的最小拼接数
孟飞阳 发表于5个月前
Java实现正整数数组的最小拼接数
  • 发表于 5个月前
  • 阅读 2
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 新注册用户 域名抢购1元起>>>   

题目:输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{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]

 

标签: java
共有 人打赏支持
粉丝 187
博文 836
码字总数 521493
作品 5
×
孟飞阳
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: