26

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

例如：-

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

有没有O(n)解决这个问题的算法。我为此想到了几种方法：-

  1. 找到最小值。给定整数（0除外）中的数字（minDIgit）并将其与MSB交换，如果MSB != minDigit。如果MSB==minDigit，然后找到下一个分钟。位并将其与最重要的但 1 位数字交换，依此类推。这可能是O(n^2)最坏的情况。
  2. 做一个array/vector并按std::pair升序对其进行排序（根据数字值；首先保留较低的索引以匹配数字值）。遍历排序后的数组。将 MSB 与第一位数字交换。如果最小的数字有对应的索引作为 MSB，则将 MSB 但 1 位与下一个最小数字交换。如果下一个 min 数字有相应的 MSB 索引但 1 位，则将 MSB 但 2 位与下一个 min 交换。位数等等。这应该是O(nlog(n))。

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

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

更新 2： 我的第二个算法可以工作（尽管对极端情况和 0 进行了更多检查），并且O(n)与counting sort. 但是@GaborSch 给出的解决方案要简单得多，所以我不会真的费心为我的算法提供正确的代码。

4

7 回答 7

18

作为准备，我们遍历数字，并在数组[10] 中标记数字的最后last位置（称为它）（包括0s）。即 O(n)。

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

如果我们在第一个位置，我们last从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。在第二次迭代中，我们迭代last，它的大小是恒定的（最多 9 个）。

您可以通过在值得开始循环时添加跟踪最小值来进一步优化算法last，但这已经是一种优化。以前的版本包含，如果您有兴趣，请查看历史记录:)

于 2013-06-18T17:34:21.187 回答
11

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

从左边开始，检查数字（以下是循环的描述）：

检查是否有一个counts小于它的数字。选择最小的一个。例外：0不允许用于第一个数字。

  • 如果有，交换，你就完成了（退出循环！）。
  • 否则将 中的数字递减counts，然后选择下一个数字。

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

对于交换，您希望使用最低有效数字（更靠右）。您可以将这些位置存储在初始查找中，也可以在交换之前从末尾开始搜索第一个匹配的数字。

于 2013-06-18T16:40:27.413 回答
5

我将从右端开始遍历数组。将右侧的数字存储为最小数字和最大数字，然后开始向左移动，如果您遇到一个新的较小数字，则将其称为潜在最小数字。如果您继续向左移动并找到较小的数字，则将较小的数字设为潜力。如果您找到更大的数字，则将最小的 int 设置为更小，并将较大的存储为 max digit。每次你达到比最小数字更大的数字时，将其设为新的最大数字。如果你到达终点，交换最大数字和最小数字。在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) 内存使用的优点。

于 2013-06-18T16:54:48.360 回答
2

这是一个简单的O(n)算法：

- Record 'false' for each of ten digit values, 0 through 9
- Work through the number's digits, left-to-right
    - If the digit value is associated with 'true' go to the next digit and continue
    - Record 'true' for this digit
    - Search all the digits to the right for the right-most, smallest digit
      (except zero for the first digit in the number)
      and swap if the lowest digit found (if any) is less than the current digit
    - If swapped, report success and stop
    - If not swapped, go to the next digit and continue
- If we reach the end of the digit list, report a lack of success and stop

这在第一次检查时可能看起来不是 O(n)，但是在意识到内部循环可以执行不超过 10 次之后，很明显这是O(n)因为O(n - 10 + 10*n) = O(11*n - 10) = O(n).

于 2013-06-18T18:09:20.033 回答
1

伪代码： O(n)

1）将数字拆分为单个数字，例如 digit[10] （如另一个答案中所述）。初始化incPos = -1。

2) 从最右边开始遍历，找到最左边递增的Pos( incPos)。即在遍历比较 k+1 元素和第 k 个元素时。因为，每个 digit[k] ≠ 0，如果digit[k] >= digit[k+1]则标记incPos为k。遍历到最左边并找到最少的incPos。

4) 如果 incPos == -1 返回 num，否则从 incPos 遍历到 n 以找到该Right-Most-Minimum数字（如下面的 BLOCK 中所述），与最右最小数字交换并返回。（肯定会有至少 1 位数字。）

E.g  
93561 ->                IncPos = 0,  Right most minimum : 1 at pos 4 
596   ->                IncPos = 1,  Right most minimum : 6 at pos 2 
10234 ->                IncPos = -1, return 10234  
93218910471211292416 -> IncPos = 0,  Right most minimum : 1 at pos 18 
98761111 ->             IncPos = 0,  Right most minimum : 1 at pos 7

5）用新数字组成数字。返回号码。

于 2013-06-18T19:06:17.200 回答
0

Karoly Horvath 算法的轻微变化

您可以在 O(n) 中对数字数组进行基数排序。

现在我们有 2 个列表：排序列表和实际列表。实际是我们的原始数组。

从左到右迭代实际，

对于每个值，从 Sorted 中弹出元素，直到我们到达一个值，该值在原始数组中的位置为 < position of actual[i]

如果排序列表的值的头部是 < actual[i] 那么我们交换并且我们完成了。否则继续。

排序在 O(n) 时间内完成。最多我们弹出排序列表总数的 n 个元素，并且我们只迭代原始列表一次，所以整个算法在时间和空间上应该是 O(n)。

当然，有一些特殊情况检查 0 与最左边的元素的交换，但这不会影响复杂性。

于 2013-06-18T17:15:53.723 回答
0

这是满足上述所有测试用例的上述问题的 Java 代码。

public static String smallestNumber(String num) {
    int length = num.length();
    char[] c = num.toCharArray();
    Map<Character, Integer> map = new HashMap<>();
    for (int i = 0; i < length; i++) {
        map.put(c[i], i);
    }
    int count = 0;
    boolean flag = true;
    int ind = -1;
    for (int i = 0; i < length; i++) {
        int min = c[i];
        for (int j = i + 1; j < length; j++) {
            if (flag) {
                if (min > c[j] && c[j] != '0') {
                    min = c[j];
                    ind = j;
                }
            } else {
                if (min > c[j]) {
                    min = c[j];
                    ind = j;
                }
            }
        }
        if (ind != -1) {
            char temp = c[i];
            int index = map.get(c[ind]);
            c[i] = c[ind];
            c[index] = temp;
            count++;
        }
        flag = false;
        if (count == 1)
            break;
    }
    return String.valueOf(c);
}
于 2018-10-06T19:39:21.797 回答