k次互换中的最大数

Question

给定一个数字 K 和表示正整数的数字字符串 str，通过对 str 的数字执行最多 K 次交换操作来构建可能的最大数字。

例一： 输入： K = 4 海峡=“1234567” 输出： 7654321 解释： 三个互换可以使 输入 1234567 到 7654321，交换 1 7、2 和 6 最后 3 和 5

我正在尝试使用两个循环来解决它。对于每个索引 i，我找到第 (i+1) 个索引到第 (N-1) 个索引之间的最大整数，其中 N 是字符串的大小。如果最大数大于arr[i]，则交换它。下面是我写的代码。

public static String findMaximumNum(String str, int k) {
        int N = str.length();
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.valueOf(str.charAt(i) + "");
        }
        int swaps = 0;
        for (int i = 0; i < N - 1; i++) {
            if(swaps == k)
                break;
            int maxIndex = findMaxInRange(arr, i + 1, N - 1);
            if (arr[i] < arr[maxIndex]) {
                swap(arr, i, maxIndex);
                swaps++;
            }
        }
        String out = "";
        for (int i = 0; i < N; i++) {
            out = out + arr[i] + "";
        }
        return out;
    }

    private static int findMaxInRange(int[] arr, int i, int j) {
        int max = Integer.MIN_VALUE;
        int maxIndex = i;
        for (int k = i; k <= j; k++) {
            if (arr[k] >= max) {
                max = arr[k];
                maxIndex = k;
            }
        }
        return maxIndex;
    }

    private static void swap(int[] arr, int i, int j) {
        System.out.println("swapping "+arr[i]+" and "+arr[j]+" from "+Arrays.toString(arr));
        int ch = arr[i];
        arr[i] = arr[j];
        arr[j] = ch;
    }

    public static void main(String[] args) {
        System.out.println(findMaximumNum("61892795431", 4));

    }

少数测试用例失败。它失败的测试用例之一是 输入： 4个 61892795431

它的正确输出是： 99876215431

MyCode 的输出是： 99876125431

我无法弄清楚输出是“99876215431”，我的方法有什么问题。请帮助我理解。非常感谢:)

Answer 1

解决这个问题的基本步骤： 0. 将字符串转换为整数数组

1. 循环K次
2. 在这个循环中，从 i+1 (LOOP VAR) 到集合的末尾并搜索更高的值
3. 当我们找到比 collection[i] 更高的值时，我们会记住它的值和索引。需要注意的重要一点是，我们想要交换最大的数字，但 i 也必须是最后一个可能的数字。
4. 在迭代结束时，我们交换元素（具有最佳索引的 i）
5. 我们完成了，剩下的就是将我们的 int 列表转换回字符串。

代码：（它是 python 因为 java 很痛苦）

def sort(swaps, string):
    l = list(map(int, list(string)))
    print(l)
    for i in range(swaps):
        best = l[i] + 1
        bestIndex = i
        for j in range(i+1, len(l)):
            if best <= l[j]:
                best = l[j]
                bestIndex = j
        print(i, bestIndex)
        l[i], l[bestIndex] = l[bestIndex], l[i]
    return "".join(map(str, l))

print(sort(4, "61892795431"))

Answer 2

你的代码是正确的。问题来自参数 4（最大交换次数）。如果使用 10，则排序成功完成。

也许更深层次的问题来自于您正在将算法的交换与您可以有效地对数字进行排序的交换进行比较。您的算法可能有效，但可能不是最有效的，因此所需的交换次数高于最佳值。

Answer 3

我有同样的问题 那么我们不能只使用选择排序技术来解决这个问题吗？ 如果不是那么为什么？