如何对N位整数执行K-swap操作以获得最大可能的数字

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次[log_2(N)用于从堆中弹出数字&N以获取最右边的索引以进行交换]

上述策略在此示例中失败:
M = 8799且K = 2
遵循我的策略,在K = 1之后我将得到M = 9798 并且在K = 2 之后得到M = 9978.但是,在K = 2之后,我得到的最大值是M = 9987.

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

Answer 1

这是一个递归函数，它对每个（当前最大）数字的可能交换值进行排序：

function swap2max(string, K) {
    // the recursion end:
    if (string.length==0 || K==0)
        return string

    m = getMaxDigit(string)
    // an array of indices of the maxdigits to swap in the string
    indices = []
    // a counter for the length of that array, to determine how many chars
    // from the front will be swapped
    len = 0
    // an array of digits to be swapped
    front = []
    // and the index of the last of those:
    right = 0
    // get those indices, in a loop with 2 conditions:
    // * just run backwards through the string, until we meet the swapped range
    // * no more swaps than left (K)
    for (i=string.length; i-->right && len<K;)
        if (m == string[i])
            // omit digits that are already in the right place
            while (right<=i && string[right] == m)
                right++
            // and when they need to be swapped
            if (i>=right)
                front.push(string[right++])
                indices.push(i)
                len++
    // sort the digits to swap with
    front.sort()
    // and swap them
    for (i=0; i<len; i++)
        string.setCharAt(indices[i], front[i])
    // the first len digits are the max ones
    // the rest the result of calling the function on the rest of the string
    return m.repeat(right) + swap2max(string.substr(right), K-len)
}