通过交换给定整数中的一对数字来找到最小整数的算法

Question

给定一个正整数（以数字数组的形式）。我们可以交换给定数字中的一对数字。我们需要返回可以获得的最小整数。注意，它应该是一个有效的整数，即不应该包含前导0。

例如:-

1. 93561 返回 13569
2. 596 返回 569
3. 10234 返回 10234
4. 120 返回 102
5. 10091 返回 10019
6. 18761119 98761111退货

这个问题是否有O（n）算法。我想出了几种方法：-

< li >找到min。给定整数(0除外)中的数字(< code>minDIgit)，如果< code>MSB！= minDigit。如果< code>MSB==minDigit，则查找下一个min。数位，并将其与除1位以外的最高有效位交换，依此类推。最坏的情况可能是 O(n^2)。 < li >生成数字和索引的< code>std::pair的< code >数组/向量,并按升序排序(根据数字值；首先为匹配的数字值保留较低的索引)。遍历排序后的数组。将MSB与第一个数字交换。如果最小数位的索引为MSB，则将MSB与下一个最小数位交换1位。如果下一个min数字对应的索引是MSB，但只有1位，那么用这个下一个min交换MSB，但只有2位。数字等等。这应该是< code>O(nlog(n))。

有人可以建议一个更好的算法。

更新1：经过一点思考，我提出的第二个算法将非常好地工作（可能除了少数可以单独处理的拐角情况外）。此外，我可以使用计数排序（根据数字值）对对（数字、索引）进行排序，这在O（n）时间内是一种稳定的排序。我的论点有缺陷吗？

更新2：我的第二个算法可以工作（尽管需要更多检查角点大小写和0），在O（n）时间内，使用计数排序。但@GaborSch给出的解决方案要简单得多，所以我不会为我的算法给出合适的代码。

Answer 1

我会从右端开始遍历数组。将右侧的数字存储为最小数字和最大数字，然后开始向左移动，如果你碰到一个新的较小的数字，将其称为潜在最小数。如果你继续向左移动，找到一个较小的数字，将较小的数字设为潜在数。如果你找到一个较大的数字，将潜在数设为最小int，并将较大的整数存储为最大数字。每次你碰到比最小数更大的数字，将其设为新的最大数字。如果你碰到结尾，交换最大数字和最小数字。在python中（这是有效的，并且是O（n））

def swap_max(digits):
    i = len(digits) - 1
    while i > 0:
        if digits[i] == 0:
            i-= 1
        else:
            break
    max_i = i
    min_i = i
    pot_i = i
    z_i   = -1
    nz_i  = i
    i = len(digits) - 1
    while i >= 0:
        if digits[i] > digits[pot_i]:
            max_i = i
            min_i = pot_i
        if digits[i] < digits[min_i] and digits[i] != 0:
            pot_i = i
        if digits[i] == 0 and z_i == -1:
            z_i = i
        if digits[i] != 0 and i > 0:
            nz_i = i
        i -= 1
    if z_i != -1 and max_i != 0 and max_i < z_i:
        min_i = z_i
        i = nz_i
        max_i = i
    elif max_i == min_i and z_i != -1:
        i = nz_i
        if i < z_i:
            min_i = z_i
            max_i = i

    v = digits[min_i]
    digits[min_i] = digits[max_i]
    digits[max_i] = v
    return digits


#TESTING THE FUNCTION
tests =   [93561,596,10234,120,10091,98761111,1001,1010,1103,120,93218910471211292416]
results = [13569,569,10234,102,10019,18761119,1001,1001,1013,102,13218910471211292496]
tests = map(list,map(str,tests))
results = map(list,map(str,results))
for i in range(len(tests)):
    res ="".join(map(str,swap_max(map(int,tests[i]))))
    print res,"".join(results[i])
    if res=="".join(results[i]):
        print "PASSED\n"
    else:
        print "FAILED\n"

这最终适用于所有示例。它还具有O（1）内存使用的优势。

Answer 2

首先计算每个数字，将其存储在一个数组中（计数[10]）。

从左侧开始，检查数字（以下是循环说明）：

检查< code >计数中是否有比它小的数字。挑个最小的。例外:第一个数字不允许< code>0。

• 如果有一个，swap，就完成了（退出循环！）
• 否则，减少计数中的数字，并转到下一个数字

对于每个数字，你做O(1)工作。所以整个算法是O(n)。

对于交换，您需要使用最低有效数字（进一步向右）。您可以在初始查找时存储这些位置，也可以在交换之前从末尾开始搜索第一个匹配的数字。

Answer 3

作为准备工作，我们遍历数字，并标记数组中数字的最后位置[10]（称为最后）（包括0秒）。那就是 O（n）。

接下来，我们开始从左到右遍历数字。对于每个位置，我们试图找到最后一个位置大于当前位置的最小数字(位置约束)。此外，该数字必须小于当前数字。

如果我们处于第一个位置，我们将从1开始在最后一个>上开始循环（否则从0

如果我们找到这样一个数字（关于位置约束），我们就交换（并中断循环）。如果我们不这样做，我们就前进到下一个数字。成本最多为O（n*9），即O（n）。

总成本为O（n）O（n）*O（9）=O（n）。

该算法如何在示例上工作：

93561 ->   it can swap in the first cycle

596   ->   skipping the first cycle, 
           then finds '6' because of the position constraint 
           (comparing position '1' with last[5] = 0, last[6] = 2)

10234 ->   does not find anything because of the position constraint

93218910471211292416 -> finds the last occurrence of '1' to replace '9'

98761111 -> it can swap in the first cycle
            (last[1] = 7, so it will change the last occurrence)

555555555555555555596 -> iterates until the '9', then you skip last[5]
            but finds last[6] as a good swap

120 ->      at pos 0 (1) cannot find a non-zero element less than 1, so skip
            at pos 1 (2) can find 0 on position 2, so we swap

同样，这里我们对数字进行一次迭代(用于预解析数据)，然后一次迭代寻找MSB。在第二次迭代中，我们迭代< code>last，它的大小不变(最多为9)。

您可以通过添加跟踪最小值来进一步优化算法，当值得在last上开始循环时，但这已经是一种优化了。prevoius版本包含它，如果您感兴趣，请查看历史记录：）