怎样才能有效地找到从一个阵列串联整数的最小整数？ [英] How can we efficiently find the minimum integer from concatenating integers in an array?

问题描述

问题：给定正整数数组，可以包含重复，发现通过连接整数获得的最低数量。例如： [3，32，321] 返回 321323

Problem: Given an array of positive integers that can contain duplicates, find the minimum number obtained by concatenating the integers. Ex: [3, 32, 321] returns 321323

除了尝试所有N！串联排列，我似乎无法找到解决这个问题的好办法。我知道下面一个很好的解决方案，但我无法理解为什么它是真实的（停止阅读这里如果你想尝试解决这个）：

Aside from trying all n! concatenation permutations, I can't seem to find a good way to solve this. I do know of a good solution below, but I'm having trouble understanding why it's true (stop reading here if you want to try and solve this):

我读的解决方案，我们可以梳理一个比较器，两个数字数组 M 和 N 通过对比拼接的数值明尼苏达州和串联纳米和排序后的数组将是串联这给人的数量的最小值，但我不明白，为什么这是真的。任何想法？

I've a read a solution where we can sort the array with a comparator that compares two numbers m and n by comparing the numerical values of the concatenation mn and the concatenation nm, and the sorted array will be the concatenation that gives the mininum number, but I can't figure out why this is true. Any ideas?

推荐答案

您可以使用类似冒泡排序的东西来解决这个问题。

You can use something similar to bubble sort to solve this.

• 首先，我们注意到了最终结果的长度是固定的。

• First, we notice that the length of the final result is fixed.

其次，其结果是，可以创建（如所有可能的串的长度是固定的，所以最小辞书也是最小数目）的最小辞书串

Second, the result is the minimum lexicographical string that you can create (as the length of all possible string is fixed, so the minimum lexicographical is also the minimum number).

假设我们有两个号 N 和 M ，如果纳米＆LT; MN，因此n应始终在M前。因为如果我们有一个字符串为m，...，N，所以我们总是可以通过交换成n此获得一个较小的字符串，... M。

Assume that we have two number n and m, and if nm < mn, so n should always be in front of m. Because if we have a string is m...n, so we can always obtain a smaller string by swapping this into n...m.

因此​​，我们继续交换数量，直到没有什么可以交换的，这是最终的答案

So we continue to swapping number until nothing can be swapped, and this is the final answer

这篇关于怎样才能有效地找到从一个阵列串联整数的最小整数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！