java - 组织 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 .

我唯一记得的限制是输入数组的长度是1 <= n <= 8 .

Answer 1

我会将其作为图搜索问题来解决。

问题定义

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

解决方案建议

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

为方便起见，以下是在 python 中实现的，但也可以在 java 中完成。

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

def get_swaps(sequence):
    swapps = collections.deque([])
    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 的更多信息 here)

def findSwap(sequence, k):
    state_queue = collections.deque([]) # Pending states which have not been explored yet
    visited     = set()
    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:
        curr_seq   = state[0]
        curr_count = state[1]
        # Getting all swaps possible
        swaps = get_swaps(curr_seq)
        # Adding to the queue and to visited set all the unvisited states
        for next_state in swaps:
            None if tuple(next_state) in visited else state_queue.append((next_state, curr_count+1)), visited.add(tuple(next_state))
        # popping next state from the queue
        try:
            state = state_queue.popleft()
            curr_seq = state[0]
            min_diff = max([abs(curr_seq[1:][ii] - curr_seq[:-1][ii]) for ii in range(len(curr_seq) - 1)])
        except IndexError:
            found = False
            break
    if found:
        return state[1]
    else:
        return -1

解释

在每个州我们:

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

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

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

设置测试数组时，我们得到:

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