-
0 votesanswersviews
给定排序整数数组，根据A [i] = i的除法和征服写一个算法
Given: 排序整数数组，整数都不同 - 没有重复 . Problem: 基于除法和征服编写算法（在运行时尽可能好），以检查是否存在数组中存在A [i] = i的索引i . 好吧，我想到了二进制搜索，它是O（logn）运行时复杂度 . 有没有比这更快的东西？ -
0 votesanswersviews
查找与O（nlogn）中的一条线具有相同距离的所有点对
我正在尝试解决算法问题 . 我有2个数组，比如A和B，包含一些点 . A和B的长度相同 . 我知道A和B中的所有点都是截然不同的 . 现在，我想找到距离一条线的距离相同的所有对 . 还有一条规则 . 我不能比较A中的2个点和B中的两个点 . 如何在O（nlogn）中解决这个问题？我认为这是一个分而治之的问题，但我找不到解决方案 . 提前致谢 . 编辑：一个例子： Line -> y=0 A... -
1 votesanswersviews
划分和征服：找到距离小于D的所有点对
给定n个点（x，y坐标），我需要使用分而治之算法找到距离小于D的所有点对 . 最初我考虑使用类似的方法作为最近点问题，但是因为现在距离D是一个常数，所以我们可以在分裂区域中无限多个点而不是最近点问题中的第8个点 . 因此运行时间为O（n ^ 2），这并不比Brute-force好 . 任何想法或提示将不胜感激 . -
4 votesanswersviews
寻找最大子阵列的分而治之算法 - 如何提供结果子阵列索引？
对不起，我有一个使用Brute Force Algorithm O(n^2)，Divide and Conquer O(nlogn)和Kadane's Algorithm O(n)解决Maximum Sub Array Problem的任务 . （我的代码不同） . “例如，对于值{-2,1，-3,4，-1,2,1，-5,4}的序列，具有最大总和的连续子数组是[4，-1， [1]，总和6.“ ... -
4 votesanswersviews
用于比较来自2个不同阵列的点的最近对算法
我想将一个数组中的点与另一个数组中的点进行比较，找到最接近的一对 . 直到现在我遇到的只有一个阵列 . 我不想比较来自同一阵列的点 . 蛮力算法有效，但速度太慢 . 是否有使用分而治之方法的算法或实现？ 编辑1：一个点被定义为地球表面上的一对（纬度，经度） . -
0 votesanswersviews
从迭代中划分和征服
给定具有n个元素的基于（1的）阵列a和函数f（i，j）（1≤i，j≤n）为（i-j）2g（i，j）2 . 函数g由以下伪代码计算： int g(int i, int j) { int sum = 0; for (int k = min(i, j) + 1; k <= max(i, j); k = k + 1) sum = sum + a[k]; return ... -
1 votesanswersviews
时间复杂度如何从强力变为递归解决方案？
这是我正在努力的问题 我实施了蛮力解决方案和分而治之（递归）解决方案 . 他们都使用这个输入（从第1到第4个） 对于暴力解决方案，我所做的是生成{1,2,3,4}的所有子集，遍历所有子集并仅检查包含1和4的子集 . 我知道我的暴力解决方案将在O（2n）时间，因为有数学上2n个子集，我必须遍历所有这些子集 . 对于我的递归解决方案 . 我所做的是打破这个问题，以便生成/将要检查的唯一解决方案是包含1... -
5 votesanswersviews
使用分而治之的方法可以提高时间复杂度，以便在数组中找到最大值和最小值
这是个问题，我在接受采访时被问到了 . 找到最小和最大数组的最佳时间复杂度是多少？ 我回答：O（n） . 遍历数组，跟踪到目前为止发现的最大值和最小值 . 非常简单直接前进 . 面试官问你可以用分而治之的方法来改善它 . 我说可能不是 . 然后谈话继续进行，最后我被要求实施分而治之的方法 . 这里是： public class MinMaxInArray { public static i... -
2 votesanswersviews
算法：分而治之（快速排序的应用？！）
关于如何处理下面的问题的任何帮助将不胜感激 . 我也对这个问题发表了一些看法 . 您是一个招收n名学生的 class 的助教 . 你有他们的最终分数（未分类），你必须为他们分配一个G可用等级（A，B，C等） . 约束是（假设n是G的倍数）：完全（n / G）学生得到每个年级（例如，如果n = 30，G = {A，B，C}，那么正好10个学生得到A，得分为10，得分为10）得分较低的学生得分不高于... -
106 votesanswersviews
分治算法与动态规划的区别
Divide和Conquer算法和动态规划算法有什么区别？这两个术语有何不同？我不明白他们之间的区别 . 请举一个简单的例子来解释两者之间的差异以及它们看起来相似的基础 . -
-1 votesanswersviews
快速排序的递归如何工作？
以下功能是快速排序的实现 . 这里我们将最后一个元素作为一个支点 . 我理解 partition 函数（其中枢轴到达其排序位置）但我无法理解递归函数 qs . 函数 qs 递归调用自身以通过 qs(a,start,pi-1) 解析左侧，并通过 qs(a,pi+1,end) 解析分区右侧 . 它解决了左边然后（左边的左边）然后（左边的左边）等，然后左边，左边......右边等等 . 或者通过解决左... -
-3 votesanswersviews
递归 - 堆栈溢出错误
给定未排序的数组，找到最大值和最小值 . 我试图以递归，分而治之的方式执行此操作，但我不断收到堆栈溢出错误 . 我调试了，我继续在递归调用中得到错误，但不知道什么是错误或如何解决它 . 我有静态的最小和最大变量 . 感谢您提供的信息和帮助！ static void findMaxMin(int[] array, int start, int end) { if (end == 2) ... -
3 votesanswersviews
一系列xy坐标中的最短距离
我有一个分配比较2个不同算法的问题 . 这是问题所在： 假设我有一系列像这样的xy坐标： A（2,3），B（5,6），C（7,8），D（6,2），E（5,5）等 . 我想找到两条距离最短的坐标 . 其中一个解决方案是使用蛮力（逐个匹配），但还有另一种使用“分而治之”方法的解决方案 . 你能帮我解决“分而治之”的方法吗？ -
-3 votesanswersviews
划分和征服最近对算法
我正在尝试创建一个算法，从随机生成的点返回最接近的一对 . 我已经完成了算法，但算法的分而治之方法并不比蛮力方法快得多 . 我该怎么做才能优化代码，使其在（n log n）时间返回？ import java.util.*; import java.lang.*; import static java.lang.Math.min; import static java.lang.StrictMath... -
0 votesanswersviews
递归函数偶尔会返回分段错误
我正在努力实现一种分而治之的算法，该算法找到彼此最接近的两个点以及它们之间的距离 . 我的最终解决方案找到了正确的答案（与使用蛮力相比），但大约1/3的时间会返回分段错误错误 . 我一直在努力解决这个问题几天，在这里和那里添加打印语句，但找不到问题 . 如果有人看了我的代码，我将不胜感激 . -
1 votesanswersviews
深入理解算法设计技术
“为给定的应用程序设计正确的算法是一项艰巨的任务 . 它需要一个重大的创造性行为，解决问题并从以太中解决问题 . 这比采取其他人的想法并修改它或将其调整为更难 . 让它变得更好 . 你可以在算法设计中做出的选择空间是巨大的，足以让你有足够的自由来悬挂自己“ . 我研究了几种基本的算法，如分而治之，动态编程，贪婪，回溯等 . 但是，当我遇到某些编程问题时，我总是无法认识到适用的原则 . 我想掌握算法... -
0 votesanswersviews
使用D＆C /递归的最大子数组
我想用一个展示（n log n）的算法实现最大子数组问题： 找到最大的连续子数组，或数组中连续元素的最大总和 . 假设：并非所有元素都是负数 我有点工作的解决方案;问题在于重叠的中心数组，以及指定重叠子问题的适当索引，一些数组我得到正确答案而不是其他问题 . 仅仅为了比较和检验正确性我实现了一个称为Kadane算法的解决方案（我相信复杂性是Omega（n）） . 这是Kandane的算法（ht... -
0 votesanswersviews
设计一种算法，使流量在网络上保持均匀分布
我的问题与如何编写特定事物或任何技术编程问题无关 . 我需要帮助开发一个我正在研究的算法逻辑，我将稍微解释一下 . 我在这里是因为我无法想象一个比stackoverflow更好的地方来帮助我，因为它已被证明是过去的最佳选择 . 我要感谢你们帮助我，给我你宝贵的时间 . 所以这是我的大脑戏弄算法： Aim : 我正在开发一种算法，旨在通过网络平均分配流量（汽车） . 我将模拟此算法以检查它在某些流量...