使用数组进行唯一行程选择的最佳执行算法？
如果给我三个长度相等的数组。每个数组表示我在公路旅行中到一个特定景点的距离(即第一个数组仅是主题公园，第二个数组仅是博物馆，第三个数组仅是海滩)。我不想确定所有可能的旅行，每次旅行都在每种类型的景点之一停留，永远不会倒车，永远不会两次参观同一个景点。
如果我有以下三个数组: 29 50 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))?)
回答 2
Stack Overflow用户
发布于 2018-04-26 17:56:55
您的解决方案在O(n ^ 3)中运行。但是如果您需要生成所有可能的组合，并且距离是按行和列排序的，即
[1, 2, 3]
[4, 5, 6]
[7, 8, 9]所有的解决方案都将降级为O(n^3)，因为它需要计算所有可能的子序列。
如果输入有大量数据，并且它们之间的距离相对较远，那么排序+二进制搜索+递归解决方案可能会更快。
static List<List<int>> answer = new List<List<int>>();
static void findPaths(List<List<int>> distances, List<int> path, int rowIndex = 0, int previousValue = -1)
{
if(rowIndex == distances.Count)
{
answer.Add(path);
return;
}
previousValue = previousValue == -1 ? distances[0][0] : previousValue;
int startIndex = distances[rowIndex].BinarySearch(previousValue);
startIndex = startIndex < 0 ? Math.Abs(startIndex) - 1 : startIndex;
// No further destination can be added
if (startIndex == distances[rowIndex].Count)
return;
for(int i=startIndex; i < distances[rowIndex].Count; ++i)
{
var temp = new List<int>(path);
int currentValue = distances[rowIndex][i];
temp.Add(currentValue);
findPaths(distances, temp, rowIndex + 1, currentValue);
}
}此解决方案中的大部分节省来自这样一个事实，即由于数据已经排序，我们不需要在下一个目的地中查找距离小于之前的值的距离。
对于更小和更接近的距离，这可能是一种过度杀伤力，因为额外的排序和二进制搜索开销使其比直接的蛮力方法慢。
归根结底，我认为这取决于你的数据是如何的，你可以尝试这两种方法，并尝试哪一种对你来说更快。
注意：此解决方案不假设严格增加距离，即[29, 37, 37]在此有效。如果你不想要这样的解决方案，你将不得不改变二进制搜索来做一个上限，而不是下限。
Stack Overflow用户
发布于 2018-04-26 14:56:23
对State使用动态编程。因为只有3个数组，所以只有2*2*2个状态。
组合数组并对其进行排序。29，37，37，50，61，70。我们做了一个二维数组: dp0..6。有8种状态：
- 001表示我们选择了第1个阵列。
- 010表示我们选择了第二个阵列。
- 011表示我们选择了第一个和第二个阵列。
- .....
- 111表示我们选择了第1、2、3个阵列。
复杂度为O(n*8)=O(n)
https://stackoverflow.com/questions/50034699
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号