Tag: 算法

查找数组中未出现两次的整数: 我试图解决这个问题：在一个整数数组中，所有数字恰好出现两次，除了一个恰好出现一次的数字。一个简单的解决方案是对数组进行排序，然后测试非重复。但我正在寻找具有时间复杂度O（n）的更好的解决方案。

米勒拉宾Primality测试准确性: 我知道Miller-Rabin素性测试是概率性的。但是，我想将它用于编程任务，不会留下任何错误。如果输入数字是64位整数（即C long long ），我们可以假设它是非常高的概率吗？

如何确定一个点是否位于矩形内？: 可能重复：找到一个点是否位于矩形内部有一个采访问题，“如何确定一个点是否位于矩形内” 请注意，矩形也可以旋转。因此，在矩形内检查点的简单解决方案在这里不起作用…… 请分享您对这个问题的看法.. 我在互联网上找到了一个链接，并试图了解它，但失败了……请问这里有什么身体可以提供完整的计算机图形逻辑解决方案，因为我已经忘记了所有的基础知识…. 如何确定一个点是否在矩形内。

一个更好的程序来评估数字的平方根: 我是C编程语言的初学者，我被赋予这个任务来编写一个程序来计算自然数的平方根，而不使用math.h或除stdio.h之外的任何其他库函数。请参阅我们在整个过程中使用int ，因此对于非平方数，我们找到n的平方根的底数。现在我制作了这个程序，但它只适用于完美的正方形，但对于非正方形，它不起作用。我在这里引用它，我希望有一些方法可以修改它。 #include main() { int a; scanf(“%d”, &a); int s = 1, l = a, mid = 0; while(s < l) { mid=(s + l)/2; if((mid * mid) == a) { break; } else if ((mid * mid) < a) { s = mid + 1; } else { l = […]

找到一对数字，其差别是未排序数组中的输入值’k’: 正如标题中所提到的，我想找到差异为K的元素对 example k=4 and a[]={7 ,6 23,19,10,11,9,3,15} output should be : 7,11 7,3 6,10 19,23 15,19 15,11 我已经读过SO中的先前post“ 在数组中找到添加到给定总和的数字对 ” 为了找到有效的解决方案，需要多长时间？时间复杂度是O(nlogn)还是O(n) ？我试图通过分而治之的技术来做到这一点，但我没有得到退出条件的任何线索…… 如果一个有效的解决方案包括使用两个指针对输入数组进行排序和操作元素，那么我认为我应该采用最小的O(nlogn) … 是否存在任何与O(n)相关的数学相关技术。任何帮助表示赞赏..

俄罗斯农民增殖: 这是我对俄罗斯农民增殖的简短实施。怎么改进？限制：仅在> 0，b> 0时有效 for(p=0;p+=(a&1)*b,a!=1;a>>=1,b<<=1);

如何确定列表是否是另一个列表的子集？: 确定列表是否是另一个列表的子集的有效方法是什么？例： is_subset(List(1,2,3,4),List(2,3)) //Returns true is_subset(List(1,2,3,4),List(3,4,5)) //Returns false 我主要寻找有效的算法，而不是太关心列表的存储方式。它可以存储在数组，链接列表或其他数据结构中。谢谢编辑：列表已排序

找到最长的重复字符串及其在给定字符串中重复的次数: 例如，给定字符串“ abc fghi bc kl abcd lkm abcdefg ”，该函数应返回字符串“ abcd ”并且计数为2。 AO（n ^ 2）解决方案似乎很容易，但我正在寻找更好的解决方案。编辑：如果没有比O（n ^ 2）更好的方法比哪种方法最好的表现明智。

生成数字的所有不同分区: 我正在尝试编写一个C代码来生成具有给定数字的不同元素的所有可能的分区（分成2个或更多部分）。给定分区的所有数字的总和应该等于给定的数字。例如，对于输入n = 6 ，具有2个或更多具有不同元素的元素的所有可能分区是： 1,5 1,2,3 2,4 我认为递归方法应该有效，但我无法处理不同元素的附加约束。非常感谢C / C ++ / Java中的伪代码或示例代码。谢谢！编辑：如果它使事情变得更容易，我可以忽略具有至少2个元素的分区的限制。这将允许将数字本身添加到列表中（例如，6本身将是一个微不足道但有效的分区）。

算法挑战：为浮点生成连续分数: （编辑：回应脾气暴躁的评论，不，这不是功课。我正在进行音调检测，获取一系列潜在的谐波峰值，并尝试构建基频的候选者。因此，它实际上是一个非常实际的问题。）考虑（例如）pi的最佳分数近似，按增加的分母排序：3 / 1,22 / 7,355 / 113，…… 挑战：创建一个整洁的 C算法，它将为给定的浮点数生成第n个商近似值a / b，同时返回差异。 calcBestFrac（float frac，int n，int * a，int * b，float * err）{…} 我认为最好的技术是持续分数拿走pi的小部分，你得到3 现在，余数是0.14159 … = 1 / 7.06251 .. 所以下一个最佳理性是3 + 1/7 = 22/7 从7.06251拿走7，你得到0.06251 ..大约1 / 15.99659 .. 称之为16，然后是下一个最佳近似值 3 + 1 /（7 + 1/16）= 355/113 但是，转换成干净的C代码远非微不足道。如果我得到一些整洁的话，我会发帖。同时，有人可能会喜欢它作为脑力激荡器。