如何对n位整数进行k交换操作以获得最大可能的个数

Question

我最近接受了一次采访，被问到了这个问题。让我适当地解释一下问题：

给定一个数M（n位整数）和K个交换操作（一个交换操作可以交换2位），设计一个算法来得到最大可能的整数？
示例:
M=132 K=1输出=312
M=132 K=2输出=321
M=7899 K=2输出=9987

我的解决方案（伪代码中的算法）。我使用max-heap在每个k操作中从n个数字中获得最大的数字，然后适当地交换它。

for(int i = 0; i<K; i++)
{
    int max_digit_currently = GetMaxFromHeap();
    // The above function GetMaxFromHeap() pops out the maximum currently and deletes it from heap

    int index_to_swap_with = GetRightMostOccurenceOfTheDigitObtainedAbove();
    // This returns me the index of the digit obtained in the previous function  
    // .e.g If I have 436659 and K=2 given,   
    // then after K=1 I'll have 936654 and after K=2, I should have 966354 and not 963654.

    // Now, the swap part comes. Here the gotcha is, say with the same above example, I have K=3.
    // If I do GetMaxFromHeap() I'll get 6 when K=3, but I should not swap it, 
    // rather I should continue for next iteration and 
    // get GetMaxFromHeap() to give me 5 and then get 966534 from 966354.

    if (Value_at_index_to_swap == max_digit_currently)
        continue;
    else
        DoSwap();
}

时间复杂度:O(k*(N+log_2(N)))
//K-times[log_2(N)用于从堆中弹出数字&N以获取最右边的索引以进行交换]

上述策略在本例中失败:
M=8799和K=2
按照我的策略，我将在K=1之后得到M=9798，在K=2之后得到M=9978。但是，在k=2之后，我能得到的最大值是M=9987。

我错过了什么？
还建议了解决问题的其他方法&优化我的解决方案的方法。

Answer 1

我认为缺少的部分是，在执行了K个交换之后，就像OP中描述的算法一样，剩下一些数字可以在它们之间交换。例如，对于数字87949，在初始算法之后，我们将得到99748。但之后我们可以“免费”互换7个和8个，即不消耗K个互换中的任何一个。这将意味着“我宁愿不把7和第二个9交换，而是和第一个交换”。

因此，要得到最大数，就需要执行OP描述的算法，记住被移到右边的数字，以及它们被移到的位置。然后，把这些数字按递减的顺序排序，放在从左到右的位置上。

这就像是将html" target="_blank">算法分为两个阶段--在第一个阶段中，您选择哪些数字应该在前面，以最大化前K个位置。然后，您确定将它们与它们所占位置的数字进行交换的顺序，从而使该数字的其余部分也最大化。

不是所有的细节都很清楚，我也不是百分之百肯定它能正确处理所有的案件，所以如果有人能打破它--去吧。