关键词：
题目：给出一个Θ(nlgn)时间的算法。判断在集合S中，是否存在两个元素的和为x。
算法导论的教师手册解法如下：
1.对集合S排序。
2.创建集合T = z : z = x − y ，y ∈ S。
3.对集合T排序。
4.去除S和T中的重复元素。
5.按照从小到大顺序或者从大到小顺序合并两个集合
6.对于合并以后的集合而言，当且仅当集合中的相邻位置出现相等元素，则存在，否则不存在。
这个解法的大致含义：假设集合T中存在一个元素w，那么w = x - y，而集合S中存在y，由于集合中已经没有重复的元素，如果集合S与集合T中的元素合并，相邻位置出现相等元素， 则表明集合S中存在w，因此w + y = x，则存在。
由于所需时间复杂度为O(nlogn)，所以我们用归并排序，Java代码如下：
private static void mergeSort(int[] arr, int lo, int hi)
if (lo < hi)
int mi = (lo + hi) / 2;
mergeSort(arr, lo, mi);
mergeSort(arr, mi + 1, hi);
rewriteMerge(arr, lo, mi, hi);
// 不使用哨兵的方法
private static void rewriteMerge(int[] arr, int lo, int mi, int hi)
int frontLength = mi - lo + 1;
int backLength = hi - mi;
int[] l = new int[frontLength];
int[] r = new int[backLength];
for (int i = 0; i < frontLength; i++)
l[i] = arr[lo + i];
for (int i = 0; i < backLength; i++)
r[i] = arr[mi + 1 + i];
int lp = 0;
int rp = 0;
for (int i = lo; i <= hi; i++)
if (lp == frontLength)
break;
if (rp == backLength)
arr[i] = l[lp];
lp++;
continue;
if (l[lp] < r[rp])
arr[i] = l[lp];
lp++;
else
arr[i] = r[rp];
rp++;
So step one 的时间复杂度为O(nlogn)。
我把step two and step three 合并在一个方法中了，Java代码如下：
private static int[] createAndSort(int[] a, int aLength, int x)
int[] aCopy = new int[aLength];
for (int i = 0; i < aCopy.length; i++)
// 我将第三步合并到这，由于a数组是有序的，通过x减去a中的最大值，放在a副本中的最小位置上
aCopy[i] = x - a[aLength - 1 - i];
return aCopy;
上面这个方法时间复杂度为O(n)。
step 4 Java代码如下：
private static int[] distinctArray(int[] a)
//定义一个临时的数组
int[] temp = new int[a.length];
//将数组中的重复元素都置为整数的最小值
for (int i = 0; i < a.length - 1; i++)
if (a[i] == a[i + 1])
a[i] = Integer.MIN_VALUE;
//定义指向temp的指针，去除数组a中的重复值，将其保存到数组temp中
//temp数组中的后面的元素有可能为空
int pot = 0;
for (int i = 0; i < a.length; i++)
if (a[i] != Integer.MIN_VALUE)
temp[pot++] = a[i];
if (pot != a.length) //如果有重复元素，去除temp数组中的空元素
int[] result = new int[pot];
for (int i = 0; i < result.length; i++)
result[i] = temp[i];
return result;
else //如果没有重复元素，则直接返回temp数组
return temp;
上面这个方法时间复杂度为O(n)。
Step 5 Java代码如下：
private static int[] mergeDoubleArray(int[] a, int[] aCopy)
int alength = a.length;
int acopylength = aCopy.length;
int[] ret = new int[alength + acopylength];
for (int i = 0; i < alength; i++)
ret[i] = a[i];
for (int i = 0; i < acopylength; i++)
ret[alength + i] = aCopy[i];
rewriteMerge(ret, 0, a.length - 1, ret.length - 1);
return ret;
上面这个方法时间复杂度为O(n)。
Step 6 Java代码如下：
private static boolean validate(int[] result)
boolean isExist = false;
for (int i = 0; i < result.length - 1; i++)
if (result[i] == result[i + 1])
return true;
return isExist;
上面这个方法时间复杂度为O(n)。
主方法Java代码如下：
public static void main(String[] args)
int[] a = 7, 4, 3, 34, 56, 34, 1 ;
int aLength = a.length;
int x = 12;
// step one
mergeSort(a, 0, aLength - 1);
// step two and step three
int[] aCopy = createAndSort(a, aLength, x);
// step four
a = distinctArray(a);
aCopy = distinctArray(aCopy);
// step five
int[] result = mergeDoubleArray(a, aCopy);
// step six
boolean isExist = validate(result);
System.out.println(isExist);
综上所述：总共所需时间为：O(nlogn) + O(n) + O(n) + O(n) + O(n) = O(nlogn)
方案二如下：
public static void main(String[] args)
int[] b = 6,6,1;
int bLength = b.length;
int y = 12;
//用归并排序为数组b排序
mergeSort(b, 0, bLength - 1);
for (int i = 0; i < b.length; i++)
Integer res = IterativeBinarySearch(b, y - b[i], 0, b.length - 1);
if ( res != -1 && res.intValue() != i )
System.out.println(true);
return;
System.out.println(false);
二分查找算法，我就不列在这里了。这个算法很简单，算法时间复杂度为O(nlogn)。
但我个人觉得，如果令x = 12，而集合S中存在一个元素6（2个元素6正确），这种算法将会导致错误的结果。希望大家看看有什么好的建议来解决这个Bug，期待您的评论。
算法导论2.3-7(代码片段)
问题：请给出一个运行时间为O(nlgn)的算法，使之能在给定一个由n个整数构成的集合S和另一个整数x时，判断S中是否存在有两个其和等于x的元素。 题目思路：先将集合S用归并排序排好序，因为归并排序的运行时间为O(nlgn)；... 查看详情
《算法导论》12.3节习题(代码片段)
12.3-1二叉搜索树insert操作的递归版本voidinsert1(Node*pRoot,Node*pAdd)boolbLeft=pAdd->key<pRoot->key;Node*pNextRoot=bLeft?pRoot->left:pRoot->right;if(pNextRoot)insert1(pNextRoot,pAdd);elsepAdd-> 查看详情
算法导论第2章编程题自选
系列地址：算法导论（CLRS）参考答案与配套编程题选练习2.3-7配套编程题：两数之和(TwoSum)-LeetCode/LeetCode-CN 查看详情
算法导论之动态规划字符串拆分问题(代码片段)
...许程序员将一个字符串。。。原题如下图，最近在刷算法导论的题目，觉得这题有趣，写下自己的想法和大家分享一下。 图1 动态... 查看详情
算法导论之快速排序(代码片段)
快速排序个人思绪很混乱,建议直接看原文简洁版:defPARTITION(A,p,r):x=A[r]#锚点主元大于它放一边，小于的放另一边i=p-1forjinrange(p,r):ifA[j]<=x:i+=1A[i],A[j]=A[j],A[i]A[i+1],A[r]=A[r],A[i+1]returni+1defQUICKSORT(A,p,r):ifp<r:#分治q=PARTIT 查看详情
算法导论之红黑树-打印销毁-非递归[c语言](代码片段)
...2716:45转载请注明来自"祁峰"的CSDN博客1引言 博文《算法导论之平衡二叉树-打印》中使用递归算法实现了平衡二叉树的打印功能，仿照此博文中的代码 查看详情
算法导论oj习题—数据库查询(红黑树实现avl树实现)(代码片段)
算法导论OJ习题—数据库查询Description勤奋的小明为了预习下学期的数据库课程，决定亲自实现一个简单的数据库系统。该数据库系统需要处理用户的数据库插入和查询语句，并输出相应的输出。具体来说，用户的输... 查看详情
算法导论答案勘误（ing）(代码片段)
第二章第四题这个应该是错的，如果(logn)^3是n的幂，那确实g5在g3前面。但现在是两个同时取log，logg3(n)=logn+3loglognlogg5(n)=(logn)^2应该是g3小 通过画图佐证之：importmathimportmatplotlib.pyplotaspltx=range(1,1 查看详情
习题—动态规划贪心算法(代码片段)
算法导论第15、16章习题—动态规划、贪心算法1.我们对钢条切割问题进行一点修改，除了切割下的钢条段具有不同价格pip_ipi外，每次切割还要付出固定的成本ccc。这样，切割方案的收益就等于钢条段的价格之和减... 查看详情
重读算法导论之算法基础
重读算法导论之算法基础插入排序?对于少量数据的一种有效算法。原理：整个过程中将数组中的元素分为两部分，已排序部分A和未排序部分B插入过程中，从未排序部分B取一个值插入已排序的部分A插入的过程采用的方式为:依次... 查看详情
《算法导论》第六章练习题exercise
6.1-1 在高度为h的堆中，元素最多有2h+1-1个，最少有2h 个。注意算法导论里的高度是指深度，从0开始而不是从1开始。 6.1-2 这很好想，但是不好证明。 由已知高度为h的堆，它的元素个数满足2h ... 查看详情
算法导论(代码片段)
1.算法在计算中的作用 1.1算法 算法解决哪些问题 数据结构 技术，算法设计分析技术 难题，PE完全问题 并行性 1.2作为一种技术的算法 效率 算法与其他... 查看详情
算法习题---线性表之单链表逆序打印(代码片段)
...链表数据使用头插法，逆序排列，然后正序打印即可三：算法实现（这里使用方法一：递归实现简单易懂）#define_CRT_SECURE_NO_WARNINGS#include<stdio.h>#include<stdlib 查看详情
数据挖掘导论——python练习(代码片段)
实验2：Python练习编写一个名为collatz()的函数,它有一个名为number的参数，如果输入的参数是质数,那么collatz()就打印出number，如果number不是质数,则打印3*number+1。代码分析测试有两个磁盘文件test1.txt和test2.txt,各存放... 查看详情
算法导论-第一个算法--插入排序(代码片段)
1INSERTION-SORT(A)2 forj=2toA.length3key=A[j]4//InsertA[j]intothesortedsequenceA[1..j-1]5i=j-16whilei>0andA[i]>key7 A[i+1]=A[i]8 i=i-19A[i+1]=key首先,算法导论书上的类代码如上述.首先要理解的是,算法导论上的类代码并不是从0开始,而是从1 查看详情
算法习题---线性表之数组实现循环移动(代码片段)
...组R中，试设计一个在时间和空间两方面都尽可能高效的算法，将R中保存的序列循环左移p（0<p<n）个位置，即把R中的数据序列由（x0，x1，…，xn-1）变换为（xp，xp+1，…，xn-1，x0，x1，…，x）。二：思考要实现R中... 查看详情
算法习题---线性表之数组主元素查找(代码片段)
一：题目主元素是指：一个数在数组中出现的次数超过数组长度的一半，那么这个数就是数组元素的主元素。例如：0,5,5,3,4,5,5,5,5,9这里面元素5有6个超过了一半，所以就是主元素使用一种高效率的方法找出数组A的主元素，若有... 查看详情
算法习题---线性表之单链表的查找(代码片段)
...针list，在不改变链表的前提下，设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数），若查找成功，算法输出该结点的data域的值，并返回1，否则，只返回0。注意：这里的链表中没有给出链表长度哟二... 查看详情