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]--;
            }
}

标签： c++arraysalgorithm

Answer 1

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

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

如果 hash[i] 有一个值，把它放在 i 并从堆中删除。如果不是，则将最大 elt 从堆中移至 i 并将其从哈希中删除。在任何一种情况下，将数组中的下一个 elt 添加到堆中。

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