Let X[1..n] and Y[1..n] be two arrays, each containing n numbers already in sorted order. Give an O(lgn)-time algorithm to find the median of all 2n elements in arrays X and Y.
page209 10.2-8
Explain how to implement doubly linked lists using only one pointer value np[x] per item instead of the usual two (next and prev). Assume that all pointer values can be interpreted as k-bit integers, and define np[x] to be np[x] = next[x] XOR prev[x], the k-bit "exclusive-or" of next[x] and perv[x].(The value NIL is represented by 0.) Be sure to describe what information is needed to access the head of the list. Show how to implenment the Search, Insert, and Delete operations on such a list. Also show how reverse such a list in O(1) time.
12 个解决方案
#1
up
#2
第一题: 将两个数组归并成一个数组(中间元素可见)
归并 算法 : 时间复杂度O(n),好像比你要求的高了
//两个数组 直接寻找中间元素::假设,X[n]<Y[1](X Y中元素各不相同) 则中间元素可知.
//由此可以子计算相交部分 求中间元素(时间复杂度最好O(0),最差O(n))
归并 算法 : 时间复杂度O(n),好像比你要求的高了
//两个数组 直接寻找中间元素::假设,X[n]<Y[1](X Y中元素各不相同) 则中间元素可知.
//由此可以子计算相交部分 求中间元素(时间复杂度最好O(0),最差O(n))
#3
1.无交集的情况简单。
如果有交集，就变成求交集的中间数，将第一个数组的相交部分二分。得到中间数，然后分析这个数在第二个数组的相交部分的位置。如果正好在中间，那么这个数就是所求的。如果有偏移，那么就可以再次求相交范围。
如果有交集，就变成求交集的中间数，将第一个数组的相交部分二分。得到中间数，然后分析这个数在第二个数组的相交部分的位置。如果正好在中间，那么这个数就是所求的。如果有偏移，那么就可以再次求相交范围。
#4
实现的时候我发现很难判定
这个递归很烦，判断何时返回好象很难，（如果用记数的方法数到n个元素的话）
我想过，但我实在理不清头绪
可不可把过程用伪代码实现？
复杂度确实是 O(lgn), 否则就不郁闷了
#5
英文看不懂
#6
有空MSN交流交流bing0672@hotmail.com
#7
以下的＂n/2＂表示n/2的整数部分
假设要查找第k大的数．
令m=floor(n/2)
一．用折半查找在A中找到第一个小于B[m]的数，设其为A[i], 那么两个数组*有(m-1)+(i-1)=m+i-2个元素小于B[n/2],即B[m]是第j=m+i-1大的数
１. 如果j=k，则B[j]为所求．
２．如果j<k, 说明要找的数不可能在B[1..j]中，
３．如果j>k, 说明要找的书不可能在B[j..n]中.
因此，B的规模变成了一半
二．用折半查找在B中找到第一个小于A[m]的数，设其为B[i], 那么两个数组*有(m-1)+(i-1)=m+i-2个元素小于A[n/2],即A[m]是第j=m+i-1大的数
１. 如果j=k，则A[j]为所求．
２．如果j<k, 说明要找的数不可能在A[1..j]中，
３．如果j>k, 说明要找的书不可能在A[j..n]中.
因此，A的规模变成了一半
上述两个步骤使得整个问题的规模缩小为一半，花去的时间为O(lgn).递归执行上述步骤即可
因此可以推出不等式：T(n)<=T(n/2)+O(lgn)，解得T(n)=O(lgn)
假设要查找第k大的数．
令m=floor(n/2)
一．用折半查找在A中找到第一个小于B[m]的数，设其为A[i], 那么两个数组*有(m-1)+(i-1)=m+i-2个元素小于B[n/2],即B[m]是第j=m+i-1大的数
１. 如果j=k，则B[j]为所求．
２．如果j<k, 说明要找的数不可能在B[1..j]中，
３．如果j>k, 说明要找的书不可能在B[j..n]中.
因此，B的规模变成了一半
二．用折半查找在B中找到第一个小于A[m]的数，设其为B[i], 那么两个数组*有(m-1)+(i-1)=m+i-2个元素小于A[n/2],即A[m]是第j=m+i-1大的数
１. 如果j=k，则A[j]为所求．
２．如果j<k, 说明要找的数不可能在A[1..j]中，
３．如果j>k, 说明要找的书不可能在A[j..n]中.
因此，A的规模变成了一半
上述两个步骤使得整个问题的规模缩小为一半，花去的时间为O(lgn).递归执行上述步骤即可
因此可以推出不等式：T(n)<=T(n/2)+O(lgn)，解得T(n)=O(lgn)
#8
更证：＂即B[m]是第j=m+i-1小的数＂
＂即A[m]是第j=m+i-1小的数＂
＂即A[m]是第j=m+i-1小的数＂
#9
to Cybergate()
Thank u！
第二个问题呢？我连怎么 用一个 pointer 实现 双向指 都想不通。
Thank u！
第二个问题呢？我连怎么 用一个 pointer 实现 双向指 都想不通。
#10
np[x] = next[x] XOR prev[x]
我的看法是用两个16b指针，分别组成32b的高位和低位，其余补0，然后异或到一个32b的整数中
你看行不行？
我的看法是用两个16b指针，分别组成32b的高位和低位，其余补0，然后异或到一个32b的整数中
你看行不行？
#11
how to implenment the Search, Insert, and Delete operations on such a list
重载这些操作就可以了！
重载这些操作就可以了！
#12
to ckacka(小红帽)
thank u
thank u
#1
up
#2
第一题: 将两个数组归并成一个数组(中间元素可见)
归并 算法 : 时间复杂度O(n),好像比你要求的高了
//两个数组 直接寻找中间元素::假设,X[n]<Y[1](X Y中元素各不相同) 则中间元素可知.
//由此可以子计算相交部分 求中间元素(时间复杂度最好O(0),最差O(n))
归并 算法 : 时间复杂度O(n),好像比你要求的高了
//两个数组 直接寻找中间元素::假设,X[n]<Y[1](X Y中元素各不相同) 则中间元素可知.
//由此可以子计算相交部分 求中间元素(时间复杂度最好O(0),最差O(n))
#3
1.无交集的情况简单。
如果有交集，就变成求交集的中间数，将第一个数组的相交部分二分。得到中间数，然后分析这个数在第二个数组的相交部分的位置。如果正好在中间，那么这个数就是所求的。如果有偏移，那么就可以再次求相交范围。
如果有交集，就变成求交集的中间数，将第一个数组的相交部分二分。得到中间数，然后分析这个数在第二个数组的相交部分的位置。如果正好在中间，那么这个数就是所求的。如果有偏移，那么就可以再次求相交范围。
#4
实现的时候我发现很难判定
这个递归很烦，判断何时返回好象很难，（如果用记数的方法数到n个元素的话）
我想过，但我实在理不清头绪
可不可把过程用伪代码实现？
复杂度确实是 O(lgn), 否则就不郁闷了
#5
英文看不懂
#6
有空MSN交流交流bing0672@hotmail.com
#7
以下的＂n/2＂表示n/2的整数部分
假设要查找第k大的数．
令m=floor(n/2)
一．用折半查找在A中找到第一个小于B[m]的数，设其为A[i], 那么两个数组*有(m-1)+(i-1)=m+i-2个元素小于B[n/2],即B[m]是第j=m+i-1大的数
１. 如果j=k，则B[j]为所求．
２．如果j<k, 说明要找的数不可能在B[1..j]中，
３．如果j>k, 说明要找的书不可能在B[j..n]中.
因此，B的规模变成了一半
二．用折半查找在B中找到第一个小于A[m]的数，设其为B[i], 那么两个数组*有(m-1)+(i-1)=m+i-2个元素小于A[n/2],即A[m]是第j=m+i-1大的数
１. 如果j=k，则A[j]为所求．
２．如果j<k, 说明要找的数不可能在A[1..j]中，
３．如果j>k, 说明要找的书不可能在A[j..n]中.
因此，A的规模变成了一半
上述两个步骤使得整个问题的规模缩小为一半，花去的时间为O(lgn).递归执行上述步骤即可
因此可以推出不等式：T(n)<=T(n/2)+O(lgn)，解得T(n)=O(lgn)
假设要查找第k大的数．
令m=floor(n/2)
一．用折半查找在A中找到第一个小于B[m]的数，设其为A[i], 那么两个数组*有(m-1)+(i-1)=m+i-2个元素小于B[n/2],即B[m]是第j=m+i-1大的数
１. 如果j=k，则B[j]为所求．
２．如果j<k, 说明要找的数不可能在B[1..j]中，
３．如果j>k, 说明要找的书不可能在B[j..n]中.
因此，B的规模变成了一半
二．用折半查找在B中找到第一个小于A[m]的数，设其为B[i], 那么两个数组*有(m-1)+(i-1)=m+i-2个元素小于A[n/2],即A[m]是第j=m+i-1大的数
１. 如果j=k，则A[j]为所求．
２．如果j<k, 说明要找的数不可能在A[1..j]中，
３．如果j>k, 说明要找的书不可能在A[j..n]中.
因此，A的规模变成了一半
上述两个步骤使得整个问题的规模缩小为一半，花去的时间为O(lgn).递归执行上述步骤即可
因此可以推出不等式：T(n)<=T(n/2)+O(lgn)，解得T(n)=O(lgn)
#8
更证：＂即B[m]是第j=m+i-1小的数＂
＂即A[m]是第j=m+i-1小的数＂
＂即A[m]是第j=m+i-1小的数＂
#9
to Cybergate()
Thank u！
第二个问题呢？我连怎么 用一个 pointer 实现 双向指 都想不通。
Thank u！
第二个问题呢？我连怎么 用一个 pointer 实现 双向指 都想不通。
#10
np[x] = next[x] XOR prev[x]
我的看法是用两个16b指针，分别组成32b的高位和低位，其余补0，然后异或到一个32b的整数中
你看行不行？
我的看法是用两个16b指针，分别组成32b的高位和低位，其余补0，然后异或到一个32b的整数中
你看行不行？
#11
how to implenment the Search, Insert, and Delete operations on such a list
重载这些操作就可以了！
重载这些操作就可以了！
#12
to ckacka(小红帽)
thank u
thank u