时间戳

首页 > 解决方案 > 将 'n' 锁与 'n' 键匹配

arrays - 将 'n' 锁与 'n' 键匹配

问题描述

有 n 个外观相同的锁和 n 个不同的钥匙。每把锁只能用给定钥匙中的一把钥匙打开。匹配每个锁键对。

我已经用蛮力方法 O(n^2) 解决了这个问题，但我想知道是否有有效的解决方案来解决这个问题。

标签： arraysalgorithm

解决方案

请检查这是否有帮助-

1）快速排序方式Θ（nlogn）：可以应用快速排序技术来解决。

为了理解逻辑，问题可以简化为具体细节。

// 选择枢轴（可以是最后一个或任何元素）进行分区。枢轴=分区（锁，低，高，keys_pivot）；

        // Now use returned pivot to partition keys - 
        // As key/lock should be at same index
        partition(keys, low, high, locks_pivot[pivot]);

        matchPairs(keys, locks, low, pivot-1);
        matchPairs(keys, locks, pivot+1, high);

例如， https://www.geeksforgeeks.org/nuts-bolts-problem-lock-key-problem/

2）散列函数O(n)：

 Add all locks to HashMap<> / plain array
 Iterate over keys to find a matching pair

例如， https://www.geeksforgeeks.org/nuts-bolts-problem-lock-key-problem-set-2-hashmap/

推荐阅读