•2.3-7 请给出一个运行为Θ(nlgn)的算法(伪码),使之能在给定一个由n个整数构成的集合S和另一个整数x时,判断出S中是否存在有两个其和等于x的元素。
解:解题思路:先对集合S进行归并排序,然后新建一个数组S1,使得S1[i] = x – S[i],再将两个数组并起来。如果在并的过程中发现有两个元素相等且两个元素一个来自S,一个来自S1,则可以确定S中存在有两个其和等于x的元素。
Find whether x exits
1、Sort(S)
2、for i <- 0 to Length(S) – 1
3、 do S1[i] <- x - S[i]
4、for i <- 0 to Length(S) – 1
5、 do Merge( S,S1 )
6、 if S[p] > S1[q]
7、 S0[k] <- S[p] p++ k++
8、 if S[p] < S1[q]
9、 S0[k] <- S[q] q++ k++
10、 if S[p] == S1[q]
11、 return true
12、return false
在第一行进行排序时,时间代价为Θ(nlgn),后来的合并过程时间代价为Θ(n),总的时间代价为Θ(nlgn)。
分享到:
相关推荐
算法导论课后习题2.3-7合并排序和思考题2-4逆序对答案源码
算法导论习题答案13.3-1,需要安装OpenOffice 打开。
算法导论习题解答算法导论习题解答算法导论习题解答算法导论习题解答算法导论习题解答
算法导论第二版课后习题,有1-26章的答案
算法导论习题答案13.3-2, 需要安装OpenOffice 打开。
英文原版 教师手册 算法导论-习题答案-含课后习题详细解答
NULL 博文链接:https://amazingidiot.iteye.com/blog/1127870
算法导论习题解答算法导论习题解答
NULL 博文链接:https://amazingidiot.iteye.com/blog/1127865
算法导论习题解答 算法导论习题解答 算法导论习题解答
算法导论习题解答算法导论习题解答算法导论习题解答算法导论习题解答
本内容包含了算法导论的习题部分所有答案!!!
算法导论----算法经典书籍----不用我多做介绍了吧。算法导论----算法经典书籍----不用我多做介绍了吧。
算法导论习题答案 算法导算法导论习题答案论习题算法导论习题答案答案 算法导论习题答案
数学建模算法与应用习题解答---程序及数据 本资源包括了完整的习题解答程序,非常值得对照运行学习!
算法导论习题解答中文版算法导论习题解答中文版算法导论习题解答中文版
上学时 一些算法导论的代码----矩阵连乘,弗洛伊德,bellman 01背包 n皇后
包括课本中所有伪代码java实现,部分习题,少部分思考题编程题实现
算法导论习题解答,相当nice,相当完整...一个字帅
柯尔曼-算法导论-第2版-习题解答 柯尔曼-算法导论-第2版-习题解答 柯尔曼-算法导论-第2版-习题解答 柯尔曼-算法导论-第2版-习题解答