0

我有一个数组-

$hubnode[1]=array(1,2,3,5,10,11,12,13,15,16,17);
$hubnode[2]=array(1,2,3,5,10,11,12,13,15,16,17);
$hubnode[3]=array(2,10,11,15);
$hubnode[4]=array(1,2,3,5,10,11,12,13,15,16,17);
$hubnode[5]=array(1,2,3,5,8,9,10,11,12,13,15,16,17);
$hubnode[6]=array(2,10,11,13,15);
$hubnode[7]=array(1,2,3,5,8,9,10,11,12,13,15,16,17);
$hubnode[8]=array(1,2,3,5,8,9,10,11,12,13,15,16,17);

我需要通过从每行取 1 个数字来制作每个可能的 8 个成员的唯一组。
在一个组中，所有 8 位数字都是唯一的。

在计数期间不能重复任何组。例如有效组是：-

$group[1]=1,2,10,3,4,11,5,8;

$group[2]=1,3,10,2,4,11,9,8;

........................ETC

4

1 回答 1

0

让我们尝试一些动态规划！

1) 如果你只有 1 个组怎么办？那么这很容易，对吧？简单的 N 种可能性，其中 N 是组的大小。例如：

$hubnode[1]=array(1,2,3);
group[1] = 1
group[2] = 2
group[3] = 3

2) 现在如果我们添加另一个组怎么办？比方说：

$hubnode[2]=数组(3,4);

你得到：

group[1] = 1,3
group[2] = 1,4
group[3] = 2,3
group[4] = 2,4
group[5] = 3,4

这向我们展示了什么？基本上，当计算 N 个集线器的组时，我们可以获取 N-1 个集线器的组，如果它不在该组中，则将来自集线器 N 的元素添加到每个集线器。

我的意思是：

  • 对于 N = 1，您有一个组“group[1] = 1”，现在您从 hub2 中一个接一个地获取所有元素，并尝试将它们应用于该组，每次创建一个新的。在这种情况下，这将创建组 {1,3} 和 {1,4}。在 group[3] 的情况下，它只创建组 {3,4} 因为 {3,3} 不满足我们关于唯一元素的条件。

3) 如果我们不能在 N 点将任何数字从集线器应用到组怎么办？好吧，我们丢弃了那个组。例如，当您有 {1,3} 然后 {1} 时，您首先获得 2 个组 1 和 3，但您不能对第一个组做任何事情，因此丢弃它。

现在的问题是如何有效地检查 X 是否在 group[Y] 中。这是一个很好的问题，因为我们不能保持组排序（因为顺序很重要），除非我们还为每个值添加一个标签到它来自哪个组。然后使用二进制搜索我们可以检查给定的数字是否在组中。

4）作为一种性能提升（如果您需要它），您可以处理从最小到最大的数组，因为最小的数组会给您可能的解决方案带来最大的限制。

在最坏的情况下，我们可以简单地线性检查每个组......

复杂性将是巨大的，但在最坏的情况下，你将有很多可能性，所以不要认为你可以做那么多......最坏的情况下，你将有 8 个组，其中有n 个不同的数字，这意味着 n^ 8，哇！

ps 正如 Ondrej 在评论部分所说，您应该尝试自己想出一些东西-我之所以回答只是因为我正在练习面试；）

于 2013-06-08T14:58:01.863 回答