组织K内所有元素所需的最小交换

Question

我最近遇到了一个编码面试问题，似乎找不到答案。问题是这样的。

给定一个整数数组，编写一个函数，返回组织数组所需的最小交换，以便每个相邻元素的差值小于或等于K。

例如

public static void main(String[] argv) {
    int[] arr1 = new int[]{10, 40, 30, 20};
    int K = 20;
    getMinimumSwap(arr1, K); // should return 1
}

它应该返回1的原因是，通过交换40和30，数组将满足给定的语句，即所有相邻元素之间的间距应在20以内。

我确实试着在谷歌上搜索答案，我想我在其他算法助手网站上找到了一些答案，但无法找到我问题的答案。失败的测试用例有一个数组3,7,2,8,6,4,5,1和K=3，它们应该返回2。

Answer 1

我将把它作为一个图形搜索问题来解决。

为了解决这个图搜索问题，我们首先需要定义系统的状态。在这种情况下，状态将是数字的序列。

定义状态后，每个图形搜索问题都可以完成这项工作，但由于您希望交换的数量最少，我们将使用BFS。

为了方便起见，下面用python实现，但也可以用java实现。

首先，我们将编写一个帮助函数，给出一个数字序列，返回该序列中所有可能的1-swap：

def get_swapps(sequence):
    swapps = []
    ii = 0
    jj = 1
    done = False
    while not done:
        temp_seq = sequence.copy()
        temp     = sequence[jj]
        temp_seq[jj] = sequence[ii]
        temp_seq[ii] = temp
        swapps.append(temp_seq)
        if jj < len(sequence)-1:
            jj += 1
        elif ii < len(sequence)-2:
            ii += 1
            jj = ii + 1
        else:
            done = True
    return swapps

请注意，这不是最好的写法，但它确实做到了。

现在我们可以实现如下BFS算法（在这里阅读更多关于BFS和DFS的内容）

def findSwap(sequence, k):
    state_queue = []  # Pending states which have not been explored yet
    visited     = []
    state    = (sequence, 0)  # Starting state, starting sequence and 0 swapps
    min_diff = max([abs(sequence[1:][ii] - sequence[:-1][ii]) for ii in range(len(sequence)-1)])
    found    = True
    while min_diff >= k:
        # saving the visited states
        visited.append(state)
        curr_seq = state[0]
        curr_count = state[1]
        # Getting all swapps possible
        swaps = get_swapps(curr_seq)
        # adding to the queue all the unvisited states
        for next_state in swaps:
            None if any([next_state == visited_state[0] for visited_state in visited]) else state_queue.append((next_state, curr_count+1))
        # popping next state from the queue
        if len(state_queue) > 0:
            state = state_queue.pop(0)
            curr_seq = state[0]
            min_diff = max([abs(curr_seq[1:][ii] - curr_seq[:-1][ii]) for ii in range(len(curr_seq) - 1)])
        else:
            found = False
            break
    if found:
        return state[1]
    else:
        return -1

在每个州，我们：

1. 生成可能的下一个状态，这是1-交换排列。
2. 对于每个下一个状态候选，我们检查是否已经访问了该状态，如果没有访问该状态，我们将下一个状态添加到状态队列中。

检查完所有可能的下一个状态后，我们从队列中弹出下一个状态，并检查最大差异。如果最大差值是lees，那么我们就完了。如果队列为空，我们搜索了所有状态空间，但没有找到解决方案，在本例中，我们将返回-1。

注意，除了状态之外，我们还携带了元组中从原始状态到该状态的交换次数。

设置测试阵列时，我们得到：

a = [3,7,2,8,6,4,5,1]
print(findSwap(a, 3))  # 2, as expected