问题标签 [divide-and-conquer]

现在我有 N 个不同的整数，我需要找到一个具有最多数字的区间，其值在 O(NlogN) 时间区间的端点之间。我称之为“分而治之”的问题，因为它属于我期末考试的“分而治之”类别。我已经考虑了 2 周并且做了很多实验，但没有一个是正确的（与蛮力算法相比）。有人可以帮助我吗？

例子：

8,1,3,4,7。答案是 1-7。

2,6,5,4,9,8。答案是 2-9 或 2-8。

我认为“间隔”这个词并不能表达我的意思。我的意思是找到数组的一个子序列，它的值在子序列的端点之间的数字最多。eg.1：“1,3,4,7”有两个数字（3,4），eg.2：“2,6,5,4,9”和“2,6,5,4,9”都有,8" 有三个数字（6,5,4）。

这是我的代码（O（n ^ 2））。@Vaughn Cato 我用它来与您的代码进行比较。

免责声明：这是一个任务。我不要求明确的代码，只需要足够的帮助来理解所涉及的算法，以便我可以修复代码中的错误。

好的，所以您可能熟悉最大子数组问题：计算并返回数组中最大的连续整数块。很简单，但这个任务需要我以三种不同的复杂度来完成：O(n^3)、O(n^2) 和 O(n log n)。我已经得到了前两个没有太多麻烦（蛮力），但第三个让我头疼......从字面上看。

我了解该算法应该如何工作：一个数组被传递给一个函数，该函数递归地将其分成两半，然后比较各个组件以找到每一半的最大子数组。然后，因为最大子数组必须完全位于左半部分或右半部分，或者位于与两者重叠的段中，所以您必须找到与左右重叠的最大子数组。比较每种情况的最大子数组，最大的将是您的返回值。

我相信我已经编写了能够充分执行该任务的代码，但我的评估似乎是错误的。我一直在尝试联系导师和助教寻求帮助，但我觉得他们中的任何一个都没有取得任何进展。以下是我迄今为止设法编写的代码。如果您发现任何明显的错误，请告诉我。同样，我不是在寻找明确的代码或答案，而是帮助理解我做错了什么。我浏览了这里介绍的所有类似案例，但没有发现任何可以真正帮助我的东西。我也做了很多谷歌搜索以寻求指导，但这也无济于事。无论如何，这是有问题的代码：

编辑：我得到的错误是不正确的结果。我的其他两种算法之间的结果一致且正确，但这个不正确。

编辑#2：这是我的代码的更新版本，精简了一点，我修复了一些东西。它仍然没有正确运行，但它应该更接近......

所以问题是找出 x 是否在按行和按列升序的排序矩阵的元素之一中。

例子 ：

1 2 3

4 5 6

7 8 9

我有兴趣找到这个问题的分而治之解决方案的时间复杂度。我用谷歌搜索了它，但我只找到了 O(m+n) 解决方案，并且还从这个Search a sorted 2D matrix中找到了。但他说（对答案发表评论）“T(R) = 3T(R/4)”，为什么 f(R) = 0？

问题是使用主定理的分而治之解决方案的复杂性是什么？在 T(R) = 3T(R/4) + f(R) 中，f(R) 应该是多少？

如果有帮助，这是我的分而治之的解决方案：

编辑以澄清解决方案：

算法： 1. 将矩阵的中间元素与搜索值进行比较 2. 如果值等于 m(i,j)，则返回 true 3. 如果值较小，则搜索矩阵的右上角、左上角、左下角的值矩阵 4. 如果值较大，则在矩阵的右上角、右下角、左下角搜索值

这个学期我有一个算法课程。一切都很好，直到我参加了关于订单统计的讲座。

这是该讲座的第一张幻灯片：

我无法理解以下内容：

什么是订单统计？

在第 i 个最小的 n 元素上是什么意思？请我需要一个例子来知道什么是“ith”！

关于这些有什么简单的解释吗？

我所知道的是这与分而治之有关，因为下一张幻灯片就是关于它的:)。

我自己解决了以下任务：

给出一个算法来找到一个索引 i 使得 1 <= i <= n 并且 A[i] = i 提供这样的索引存在。如果有任何这样的索引，算法可以返回其中的任何一个。

我使用了分而治之的方法，结果我得到：

首先想问一下是否正确？我猜是....

在这种情况下，递归 T(n) 是多少？

我相信：

2T(n/2) + O(1) ----> 对吗？谁能详细解释一下如何应用主定理解决递归？

a=2 b=2 f(n)=1 n^logba = n ---> n vs 1 所以我们有 CASE 1 导致 O(n) -> ???? 对？

我们开始在我的数据结构课程中使用分而治之的算法，我在完全理解我应该做什么时遇到了很多麻烦。下面是基本上要求我编写一个对数组求和的程序，但它必须划分并征服它，直到基数为 4，我认为这意味着将数组以 4 的块加在一起，然后将所有块在一起。我什至不知道从哪里开始。我只需要一点解释和理解。老师帮不上什么忙。该数组包含一行数字，其数量为 2 的次方，小于 1000

问题 编写一个分治算法，对一个包含 n 个整数的数组求和。该算法的基本情况是子问题的大小小于或等于 4，在这种情况下，您将使用迭代循环来对子问题的整数求和。您需要执行以下操作：

这是我的测试分治程序，但它给了我一个错误。我正朝着正确的方向前进？

这是 getSum.sumArray(getSum.java:16) 线程“main”java.lang.StackOverflowError 中的错误异常

我正在寻找一个简单的例子，将 16 个数组分解为基本情况 4。我无法完全理解如何吐出数组，然后再次拆分它。然后最后合并所有的拆分。

我一直在尝试学习分而治之的算法，并且我想出了我认为可以使用 java 的方法。该算法应该采用一个大小为 n 的数组，它是以 2 为底数。它应该将数组划分为 4 的基本情况，然后将这些索引相加。然后它将所有这些加在一起以找到整个数组的总和。这是我到目前为止在java中所做的以及我的错误。对于分而治之的算法，我至少在正确的轨道上吗？

引发异常：

这是代码：

我正在尝试解决著名的天际线问题（见 gif）：

输入

(1,11,5), (2,6,7), (3,13,9), (12,7,16), (14,3,25), (19,18,22), (23) ,13,29), (24,4,28)

应该返回，其他建筑物后面的点应该消失，并且 Y 轴变化的坐标应该在返回的天际线中：

(1, 11), (3, 13), (9, 0), (12, 7), (16, 3), (19, 18), (22, 3), (23, 13), (29 , 0)

我试图通过对算法使用分而治之的方法来实现 O(n lg n) 的运行时间，但我被困在合并部分。

每次我想起来我都会感到困惑。例如，我检查天际线首先是哪一个，例如哪个具有较低的 x 坐标，然后我将 + 它的高度添加到我的新天际线。但是后来我遇到了在另外两个天际线后面的天际线，我怎样才能检测到这种“碰撞”？

我是否首先通过检查 left.x2 < right.x1 来检查天际线是否有任何重叠？但后来我想我应该先检查什么？x 轴上的优先级重叠，一切都变成了一个巨大的鸡蛋混乱。

也许我想得太复杂了？我需要的是一组最高的 y 坐标，在每个路口，我应该这样接近它吗？

我需要计算列表中字符串之间的余弦相似度。例如，我有一个超过 1000 万个字符串的列表，每个字符串都必须确定其自身与列表中每个其他字符串之间的相似性。我可以用来高效快速地完成此类任务的最佳算法是什么？分治算法是否适用？

编辑

我想确定哪些字符串与给定字符串最相似，并且能够拥有与相似度相关的度量/分数。我认为我想做的事情与最初不知道集群数量的集群一致。