问用Θ(nlogn)编写算法
EN

Stack Overflow用户

提问于 2010-06-19 18:37:47

回答 1查看 478关注 0票数 2

我为自己写了这段代码(这不是家庭作业)，我想知道这是正确的吗?谢谢

具有时间Θ(nlogn)的算法，它可以提供n个成员的数组，以确定数组中是否有两个等于x的元素，然后返回这些元素

Algorithm Sum(arr,1,n):
MergeSort(arr)
For i<-- 1 to n
    m<-- BinarySearch(arr,arr[i],i+1,n)
return m and arr[i]   
//end of the sum algorithm

Algorithm BinarySearch(arr,arr[i],p,q)
J<--[p+q/2]
If (arr[j]+arr[i]=x)
       Return arr[j]
else if (i<j)
       Return BinarySearch(arr,arr[i],p,j-1)
else 
       Return BinarySearch(arr,arr[i-j],j+1,q)
 // end of BinarySearch algorithm

algorithm

analysis

回答 1

Stack Overflow用户

回答已采纳

发布于 2010-06-19 18:51:25

你的二进制搜索不正确。

你不应该比较i和j，你应该比较它们的和。此外，如果您对x - arr[i]进行二进制搜索，则会更容易。

Algorithm BinarySearch(arr,arr[i],p,q)
if (p == q)
    if (arr[p] == x - arr[i])
        return p
    else
        return NO_SOLUTION
j<--[(p+q)/2] // you forgot parentheses
If (arr[j] = x - arr[i]) 
       Return arr[j] 
else if (arr[j] > x - arr[i]) // our number is too big, restrict the search to smaller numbers
       Return BinarySearch(arr,arr[i],p,j)
else 
       Return BinarySearch(arr,arr[i],j+1,q) // arr[i] doesn't change

此外，您还不断地在main函数中重写m。你需要这样的东西：

Algorithm Sum(arr,1,n):
MergeSort(arr)
m = NO_SOLUTION
For i<-- 1 to n - 1
    if (m = NO_SOLUTION)
        m<-- BinarySearch(arr,arr[i],i+1,n)
    else
        break;

if (m = NO_SOLUTION)
    return NO_SOLUTION
else
    return m and arr[i]

这可以确保你在找到解决方案后停下来。在您的例子中，算法总是返回NO_SOLUTION，因为没有任何东西可以对最后一个元素进行分组。此外，出于同样的原因，您只需转到n - 1。

票数 4

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/3075192

复制

相似问题

问用Θ(nlogn)编写算法
EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问用Θ(nlogn)编写算法EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问用Θ(nlogn)编写算法
EN