1

这是一个家庭作业。

目标是用伪代码提供一种算法，该算法将搜索数字数组（不指定整数或 > 0）并检查任何两个数字的比率是否等于给定的 x。时间复杂度必须低于 O(nlogn)。

我的想法是对数组进行归并排序（O(nlogn) 时间），然后如果 |x| > 1 开始按降序检查每个数字（使用二进制遍历算法）。检查每个数字也应该花费 O(logn) 时间，最坏的情况是 n 次检查总共需要 O(nlogn)。如果我没有遗漏任何东西，这应该给我们一个 O(nlogn) + O(nlogn) = O(nlogn) 的最坏情况，在分配的参数内。

我意识到排序后从哪里开始检查比率并不重要，但时间成本按 1/2 摊销）。

我的逻辑正确吗？有更快的算法吗？

一个例子，以防不清楚：

给定一个数组 { 4, 9, 2, 1, 8, 6 }

如果我们要搜索比率为 2：

  1. 合并排序 { 9, 8, 6, 4, 2, 1 }

  2. 由于给定的比率 >1，我们将从左到右搜索。

2a. 第一个数字是 9。检查 9 / 4 > 2。检查 9/6 < 2 下一个数字。2b。第二个数字是 8。检查 8 / 4 = 2。完成

4

4 回答 4

2

要解决这个问题，只需要 O(nlgn) 就足够了

第一步，对数组进行排序。花费 O(nlgn)

step 2，检查比例是否存在，这一步只需要o(n)

你只需要两个指针，一个指向第一个元素（最小的），另一个指向最后一个元素（最大的）。

计算比率。

如果比率大于指定的比率，则将第二个指针移动到其前一个元素。

如果比率小于指定的比率，则将第一个指针移动到其下一个元素。

重复上述步骤，直到：

  1. 你找到确切的比例，或者

  2. 第一个指针到达终点，或者第二个指针到达起点

于 2012-12-31T05:27:56.037 回答
2

您提出的分析是正确的，是解决此问题的绝佳方法。排序确实在 O(n log n) 时间内起作用，并且 2n 二进制搜索也需要 O(n log n) 时间。也就是说，我认为您不想在这里使用“摊销”一词，因为它指的是不同类型的分析。

作为如何加快解决方案速度的提示，您的解决方案的总体思路是可以有效地查询任何数字，该数字是否存在于数组中。这样，您可以遍历所有数字并寻找任何可以使比率起作用的东西。但是，如果您在数组外部使用支持快速访问的辅助数据结构，则可能会以增加内存使用量为代价来减少运行时间。尝试考虑哪些数据结构支持非常快速的访问（例如，O(1) 查找），看看您是否可以在这里使用它们中的任何一个。

希望这可以帮助！

于 2012-12-30T19:46:00.863 回答
1

(1) 建立这个数组的hashmap。时间成本：O(n)

(2) 对于每个元素 a[i]，在 HashMap 中搜索 a[i]*x。时间成本：O(n)。

总成本：O(n)

于 2013-01-03T21:50:05.977 回答
1

你的算法的复杂度是 O( n²)，因为在对数组进行排序之后，你迭代每个元素（最多n次）并且在每次迭代中你最多执行n - 1个除法。

相反，在对数组进行排序后，遍历每个元素，并在每次迭代中将元素除以比率，然后查看结果是否包含在数组中：

  • 除法：O(1)
  • 在排序列表中搜索：O(log n )
  • 对每个元素重复：n次

导致时间复杂度 O( n log n )

在您的示例中：

  • 9/2 = 4.5（未找到）
  • 8/2 = 4（找到）
于 2012-12-30T19:49:05.813 回答