侧边栏壁纸
博主头像
孔子说JAVA博主等级

成功只是一只沦落在鸡窝里的鹰,成功永远属于自信且有毅力的人!

  • 累计撰写 285 篇文章
  • 累计创建 125 个标签
  • 累计收到 4 条评论

目 录CONTENT

文章目录

算法:把数组排成最小的数

孔子说JAVA
2019-10-15 / 0 评论 / 0 点赞 / 68 阅读 / 1,359 字 / 正在检测是否收录...

1、题目

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

2、思路

我们需要定义一种新的比较大小规则,数组根据这个规则可以排成一个最小的数字。

  • 排序规则:两个数字m和n,我们比较mn和nm的大小,确定在新的比较规则下n和m的大小关系,以确定哪个应该排在前面。

  • 步骤:将整型数组转换为String数组。在新的规则下对数组进行排序(本例使用了选择排序)。

3、JAVA实现

public class MinNumber {
	/**
	 * 打印组成的最小数
	 * 
	 * @param arr 数组
	 * @return
	 */
	public static String printMinNumber(int[] arr) {
		if (arr == null || arr.length == 0) {
			return "";
		}
		int len = arr.length;
		String[] strArr = new String[len];
		for (int i = 0; i < len; i++) {
			strArr[i] = String.valueOf(arr[i]);
		}
		for (int i = 0; i < len; i++) {
			for (int j = i + 1; j < len; j++) {
				if (compare(strArr[i], strArr[j])) {
					String temp = strArr[i];
					strArr[i] = strArr[j];
					strArr[j] = temp;
				}
			}
		}
		StringBuilder sb = new StringBuilder(len);
		for (int i = 0; i < len; i++) {
			sb.append(strArr[i]);
		}
		return sb.toString();
	}

	/**
	 * 比较两个字符串数值的大小(从前往后比较) example: 32 > 123
	 * 
	 * @param s1
	 *            数字字符串1
	 * @param s2
	 *            数字字符串2
	 * @return
	 */
	private static boolean compare(String s1, String s2) {
		int len = s1.length() + s2.length();
		String str1 = s1 + s2;
		String str2 = s2 + s1;
		for (int i = 0; i < len; i++) {
			int num1 = Integer.parseInt(str1.substring(i, i + 1));
			int num2 = Integer.parseInt(str2.substring(i, i + 1));
			if (num1 > num2)
				return true;
			if (num1 < num2)
				return false;
		}
		return false;
	}
	
	public static void main(String[] args) {
		int[] arr = {2,3,42,321,123,231};
		System.out.print("数组"+Arrays.toString(arr));
		System.out.println(" 组成的最小整数 "+printMinNumber(arr));
	}
}

// 数组[2, 3, 42, 321, 123, 231] 组成的最小整数 1232231321342
0

评论区