4

这是一个面试问题（我在论坛上看到它，但无法找出最佳解决方案）。问题是从给定的一组数字中找到最短路径。

例如。

Set A - [2, 14, 34]
Set B - [9, 13]
Set C - [15, 22, 62, 78]
Set D - [16, 24, 54]
Set Z - [17, 38, 41]

1）可以有任意数量的集合

2）集合内的数字永远不会重复。

3）数字的范围可以从任何开始到任何结束（它们不在0 - n之间，即它可以从1091开始到1890等）

4) 所有的集合都被排序。

在上面的示例中，路径将是：

B[13] -> A[14] -> C[15] -> D[16] -> Z[17]

最短路径定义为MAX number (17) - MIN Number (13) = 4；

有任何想法吗 ？

4

5 回答 5

3

制作一个对 [number, name_of_set] 的列表。解决。

对于给定的路径长度 D，扫描排序列表，保留 2 个指针。始终增加第一个指针，并在扩展大于 D 时增加第二个指针。扫描时，保持属于每个集合的指针之间的元素计数。如果每个集合中都有元素，宾果游戏，你找到一条最多不同的路径 D.

现在，对 D 进行二分搜索。

整体复杂度 O(N log N)

于 2012-07-27T12:30:06.887 回答
1

堆（优先队列）可能会有所帮助。

  1. 将所有数据归并排序到一个数组 N 中，同时保留原始集合 id，假设总共有 m 个集合；
  2. int 最短 = MAX(N) - MIN(N); // 即 N[N.length - 1] - N[0]
  3. 初始化一个堆 h；
  4. 用 i 循环遍历 N，如果 h 不包含与 N[i] 相同的集合中的元素，则将 N[i] 添加到堆中；如果 h 已经包含来自同一集合的元素，例如 h[k]，则将 h[k] 的键增加到 N[i]。如果 h.size() == m, shortest == N[i] - h[0] < shortest ? N[i] - h[0]：最短。

这是代码：

mergesort(all_sets[], H, S); // H holds all data, S holds corresponding setid.
Heap<key, setid> H = new Heap<key, setid>();
int shortest = N[N.length - 1] - n[0];
for(int i = 0; i < N.length; i++)
{
   int data = N[i];
   int setID = S[i];
   int hindex = H.elementFromSet(setID);
   if(hindex < 0)
    { // H does not have any element from set with setID;
       H.add(data, setID);
    } else {
       H.increase(data, hindex);
    }
    if(H.size() == m)
    {
       shortest = shortest > N[i] - H[0]? N[i] - H[0] : shortest;
    }
}

也许我可以使用哈希表来跟踪集 id 到堆索引。

我相信的运行时间是O(nlgm)。

于 2012-07-29T06:59:50.753 回答
0

您可以应用与我在此问题中描述的算法基本相同的想法。

让我们寻找最终子集的中心。它必须最小化到每个集合的最大距离。像往常一样，点到集合的距离定义为点到集合元素之间的最小距离。

对于每个集合i，fi描述到集合的距离的函数是分段线性的。如果 a,b 是两个连续的数字，那么这些关系fi(a) = 0, fi((a+b)/2) = (b-a)/2, fi(b) = 0让我们可以fi在线性时间内建立对所有数字的描述。

但是我们也可以在线性时间内计算两个分段函数的最大值fi，fj通过考虑它们是线性的连续区间 [a,b]：结果是线性的，或者通过添加唯一的交点是分段线性的分区的功能。由于我们函数的斜率始终为 +1 或 -1，因此交点是半整数，因此可以用浮点（或定点）算术精确表示。

凸性论证表明，g所有的最大值最多fi只能有 的两倍多的点fi，因此我们不必担心最大值的点数会是集合数的指数。

所以我们只是：

  1. 计算 的分段线性距离函数fi。i = 1..p
  2. 通过重复计算最大值来计算所有的最大值g。fi
  3. 的任何最小点的位置g都是所需的中心。
  4. 对于每组，选择离中心最近的点。
  5. 我们选择的点集的宽度恰好是g:-)

如果集合的数量是有界的，复杂性是 O( N )，如果集合的数量p是可变的，复杂性是 O( N p )。通过聪明地计算最大值（分而治之），我认为您甚至可以将其减少到 O( N log p )。

于 2012-07-27T13:07:25.120 回答
0

  1. 取 A 组和 B 组。在这个集合中找到最短路径。这将是 14-13 。现在对其进行排序，使其变为 13-14。现在短集 short = {13,14}

  2. 取短集 { 13, 14} 并设置 C {15,22,62,78}。现在开始节点是 13，结束节点是短集中的 14。从末端节点 14 开始，最短可达路径是 15。因此将 15 添加到短集。现在短集变为 {13, 14, 15}，对其进行排序使其保持 {13, 14, 15}

  3. 现在取短集 {13,14,15} 和集 D { 16 , 24 , 54} 短集中的结束节点是 15。所以我们从那里开始。现在从 25 到集合 D 的最短路径是 16。所以将 16 添加到短集合中。现在短集变为 { 13,14,15,16}。解决 。它仍然是 {13,14,15,16}

3. 我们可以对整个集合重复此操作以获得最终的短集合。

于 2012-07-27T11:11:42.623 回答
0

这是问题的另一种表述。

问：从所有集合中找出包含一个元素的最小区间。

A：

  1. 将所有元素放在一个桶中并对其进行排序。复杂度 O(N*K)
  2. 我们将通过二分搜索找到最大的数字，使得每个集合中至少有一个元素高于这个数字。这将是 MIN。
  3. 类似地，通过二分搜索找到最小的数字，使得每个集合中至少有一个元素小于这个数字。这将是 MAX。

作为优化，您可以将每个集合存储为一个区间，并在第 2 步和第 3 步中使用区间树进行查询。这样，查询复杂度从 O(K) 变为 O(log K)

于 2012-07-28T14:23:22.110 回答