c++ - 每个数字最大的数字最多只交换 K 次并且只交换相邻的数字

Question

我做了一个测试，还有一个问题我还是解决不了。
给定一个数字数组，每个元素最多有 K 个交换，并且只有相邻的交换，找到最大的字典顺序。
例如:

Input
[7, 1, 2, 3, 4, 5, 6]
swapTime = 2

Output
[7, 3, 4, 1, 2, 6, 5]

起初我以为它是修改后的 BubbleSort，但它不正确，有什么想法吗？这是伪代码:

void findMaxNum(int num[], int swapTime) {
    int table[n];
    for(i=0; i<n; ++i) 
        table[i] = swapTime;

    for(i=0; i<n-1; ++i)
        for(j=0; j<n-i-1; ++j)
            if(table[j]!=0 && num[j]<num[j+1]) {
                swap(num[j], num[j+1]);
                swap(table[j], table[j+1]);
                table[j]--;
                table[j+1]--;
            }
}

Answer 1

您可以使用大小为 k+1 的最大堆，最初具有前 k+1 个值和从每个索引到该索引最左边合法元素的散列(忽略索引 <= k)。

然后我们按升序对每个索引 i 执行以下操作:

如果 hash[i] 有值，将它放在 i 并从堆中移除。如果不是，则将最大 elt 从堆移到 i 并将其从散列中删除。无论哪种情况，都将数组中的下一个 elt 添加到堆中。

散列保证没有元素向右移动超过 k 个。最小堆选择最大合法元素，同时保证没有元素向左移动超过k。