如果给我三个相等长度的数组。每个阵列代表到特定景点的距离（即，第一个阵列仅是主题公园，第二个阵列仅是博物馆，第三个阵列仅是海滩），这是我要参加的公路旅行的距离。我不会确定所有可能的旅行都在每次旅行中的每种吸引力中的一种停止，永不向后行驶，也永远不会两次访问相同的吸引力。IE浏览器，如果我有以下三个数组：[29 50] [61 37] [37 70]该函数将返回3，因为可能的组合为：（29,61,70）（29,37,70）（50,61,70）到目前为止，我得到的是：public int test（int [] A，int [] B，int [] C）{ int firstStop = 0; int secondStop = 0; int thirdStop = 0; List<List<int>> possibleCombinations = new List<List<int>>(); for(int i = 0; i < A.Length; i++) { firstStop = A[i]; for(int j = 0; j < B.Length; j++) { if(firstStop < B[j]) { secondStop = B[j]; for(int k = 0; k < C.Length; k++) { if(secondStop < C[k]) { thirdStop = C[k]; possibleCombinations.Add(new List<int>{firstStop, secondStop, thirdStop}); } } } } } return possibleCombinations.Count();}这适用于以下测试用例：测试示例：（[[29，50]，[61，37]，[37，70]）OK返回3测试示例：（[5]，[5]，[5]）OK返回0测试示例：（[[61，62]，[37，38]，[29，30]）FAIL返回0什么是正确计算此算法的正确算法？什么是性能最好的算法？我如何分辨该算法的时间复杂度（即O（N * log（N）））的性能？
3 回答
慕后森
TA贡献1802条经验 获得超5个赞
更新：该问题已用新的细节重写，但仍然是完全不清楚和自相矛盾的。尝试澄清原始张贴者的问题的尝试均未成功，并且原始张贴者承认在理解问题之前已开始进行编码。下面的解决方案对于最初说明的问题是正确的；没有人可以说出解决实际问题的方法是什么样的，因为没有人可以说出真正的问题是什么。我出于历史目的将其保留在此处。
让我们重新说明问题：
我们给出了沿道路到景点的三个距离阵列。
我们希望列举出所有不会倒退的景点的可能停靠点的顺序。（注：这个问题的声明一一列举;错误的算法给出计数它们。这是完全不同的问题计数他们可以非常快速枚举他们是极其缓慢如果问题是计数，然后他们。！厘清问题）
问题中没有其他限制。（例如，问题不在于我们停在不超过一个海滩上，或者我们必须停在每种海滩上，或者我们必须在去博物馆之前先去海滩。如果这些是约束，那么必须在问题中加以说明）
假设总共有n个景点。对于每个景点，我们要么参观，要么不参观。似乎有2 n种可能性。但是，有一个问题。假设我们有两个博物馆，分别位于M1和M2，距离博物馆都只有5公里。可能的路线是：
(Start, End) -- visit no attractions on your road trip
(Start, M1, End)
(Start, M2, End)
(Start, M1, M2, End)
(Start, M2, M1, End)
有五种不可回溯的可能性，而不是四种。
您想要的算法是：
按距离对景点进行分区，以便所有分区都包含相同距离的景点。
对于每个分区，生成该分区内所有子集的所有可能排序的集合。不要忘记“跳过所有这些”是可能的命令。
所需的组合是所有分区顺序集的笛卡尔乘积。
那应该给您足够的提示以取得进展。您在这里要解决几个问题：分区，在分区内进行置换，然后取任意多个集合的叉积。 我和其他许多人都撰写了有关所有这些主题的文章，因此，如果您不知道自己如何解决这些子问题，请进行一些研究。
至于渐近性能：如上所述，给出的问题是列举解决方案。如前所述，对于相同距离处没有吸引力的情况，最好的情况是2 n，因此我们至少是指数的。如果发生冲突，那么它将成为许多阶乘的乘积。我把它留给你解决，但这很大。
再说一遍：如果问题在于找出解决方案的数量，那就容易多了。您不必枚举它们即可知道有多少解决方案！只需弄清楚每个分区的排序数量，然后将所有计数相乘即可。我剩下的工作是弄清楚分区的渐近性能，计算顺序的数量，然后将它们相乘作为练习。
- 3 回答
- 0 关注
- 151 浏览
添加回答
举报
0/150
提交
取消