标签：ret   网络   shu   个数   思路   快速   一个   value   code   

我的LeetCode：https://leetcode-cn.com/u/ituring/

我的LeetCode刷题源码[GitHub]：https://github.com/izhoujie/Algorithmcii

LeetCode 面试题45. 把数组排成最小的数

题目

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

示例 1:

输入: [10,2]
输出: "102"

示例?2:

输入: [3,30,34,5,9]
输出: "3033459"

提示:

• 0

说明:

• 输出结果可能非常大，所以你需要返回一个字符串而不是整数
• 拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

要想最终拼接值最小，需要尽可能把较小的数拼接在前面；
只要能保证两个数拼接后最小那么最终拼接的数就是最小的，所以问题可以转化为对nums的排序，排序的逻辑是两个数拼接后获得较小值时拼接在前的那个数“较小”；
比较的实现方式：

• 两个字符串的拼接比较，字符串的拼接比较结果与值的比较一致；
• 直接自定义实现两个数的比较逻辑；

思路1-转为字符串拼接比较

步骤：

1. 把nums转为String类型的list，然后利用Collections.sort对list进行排序，需要实现Comparator的比较逻辑为字符串的拼接比较；
2. 将排序后的list拼接返回；

算法复杂度:

• 时间复杂度： $ {\color{Magenta}{\Omicron\left(nlogn\right)}} $ 快排的耗时
• 空间复杂度： $ {\color{Magenta}{\Omicron\left(n\right)}} $ list需要的空间

思路2-自定义int的比较逻辑

步骤：

1. 对nums进行快排，比较的逻辑为自定义实现；
   • 对于两个数num1和num2，各自的最高位权分别为base1和base2，那么比较的逻辑为：\(num1*base2+num2；
   • 例子，对于45和336，最高位权分别为100和1000，比较的逻辑为：\(45*1000+336；
2. 将排序后的nums用StringBuilder拼接返回；

算法复杂度:

• 时间复杂度： $ {\color{Magenta}{\Omicron\left(nlogn\right)}} $ 快排耗时
• 空间复杂度： $ {\color{Magenta}{\Omicron\left(n\right)}} $ StringBuilder需要的空间

算法源码示例

package leetcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/**
 * @author ZhouJie
 * @date 2020年5月5日 下午9:15:03 
 * @Description: 面试题45. 把数组排成最小的数
 *
 */
public class LeetCode_Offer_45 {

}

class Solution_Offer_45 {
	/**
	 * @author: ZhouJie
	 * @date: 2020年5月5日 下午9:19:34 
	 * @param: @param nums
	 * @param: @return
	 * @return: String
	 * @Description: 1-转为String，然后排序，比较逻辑为：拼接后的字符串小的排在最前面（字符小对应的数值也小）；
	 *
	 */
	public String minNumber_1(int[] nums) {
		List list = new ArrayList();
		for (int val : nums) {
			list.add(String.valueOf(val));
		}
		// 转为String后对每两个字符串拼接后比较排序；
		Collections.sort(list, new Comparator() {
			@Override
			public int compare(String o1, String o2) {
				// 字符拼接后的比较结果与值的拼接比较结果一致
				return (o1 + o2).compareTo(o2 + o1);
			}
		});
		return String.join("", list);
	}

	/**
	 * @author: ZhouJie
	 * @date: 2020年5月5日 下午9:28:53 
	 * @param: @param nums
	 * @param: @return
	 * @return: String
	 * @Description: 2-重写int的sort排序，然后StringBuilder拼接；
	 *
	 */
	public String minNumber_2(int[] nums) {
		quickSort(nums, 0, nums.length - 1);
		StringBuilder sb = new StringBuilder();
		for (int val : nums) {
			sb.append(val);
		}
		return sb.toString();
	}

	/**
	 * @author: ZhouJie
	 * @date: 2020年5月5日 下午11:50:33 
	 * @param: @param nums
	 * @param: @param start
	 * @param: @param end
	 * @return: void
	 * @Description: 快速排序
	 *
	 */
	private void quickSort(int[] nums, int start, int end) {
		if (start >= end) {
			return;
		}
		int i = start, j = end, mid = nums[start];
		while (i  0) {
			base1 *= 10;
		}
		while (num2 / base2 > 0) {
			base2 *= 10;
		}
		return (num1 * base2 + num2) >= (num2 * base1 + num1);
	}

}

LeetCode 面试题45. 把数组排成最小的数

标签：ret   网络   shu   个数   思路   快速   一个   value   code   

原文地址：https://www.cnblogs.com/izhoujie/p/12835788.html