初学的算法小问题，给点提示，呵呵

Question

有2个已有序的LinkedList<Integer>，size分别为m,n。
现在要找出在2个LinkedList<Integer>合并后第K大的，要求复杂度在O(lg m + lgn)。。
给点提示吧，，呵呵

Answer 1

比如：
LinkedList<Integer> aa = new LinkedList<Integer>();
for (int i = 0; i < 10; i++) {
aa.add(i);
} LinkedList<Integer> bb = new LinkedList<Integer>();
for (int i = 6; i < 16; i++) {
bb.add(i);
}现在要找出在aa和bb里面的第K个大的数，比如K=8的话，那么要找出来的数是6
呵呵

Answer 2

用数组是可以实现O(lgm+lgn)的
但用LinkedList就不可能了 LinkedList本身就是用链接表做的 
直接在一个有序的链接表中找第k大的数就已经是O(n)了

Answer 3

import java.util.Scanner;public class Main {
public static int fd(int[] arrA, int al, int ar, int[] arrB, int bl, int br, int k) {
int am = (ar - al) / 2 + al;
int bm = (br - bl) / 2 + bl;
if( am+bm < k ) {
if( arrA[am+1] < arrB[bm+1] ) {
if( ar-am == 1 ) am = ar;
return fd(arrA, am, ar, arrB, bl, br, k);
}
if( br-bm == 1 ) bm = br;
return fd(arrA, al, ar, arrB, bm, br, k);
} else if( am+bm == k ) {
if( arrA[am] == arrB[bm] ) return arrA[am];
if( arrA[am] < arrB[bm] ) {
if( arrA[am] >= arrB[bm-1] ) return arrA[am];
if( arrA[am+1] < arrB[bm] ) return fd(arrA, am, ar, arrB, bl, bm, k);
else return arrB[bm];
}
// arrA[am] > arrB[bm]
if( arrA[am-1] <= arrB[bm] ) return arrB[bm];
if( arrA[am] > arrB[bm+1] ) return fd(arrA, al, am, arrB, bm, br, k);
else return arrA[am];
} else { // am+bm > k
if( arrA[am] < arrB[bm] ) return fd(arrA, al, ar, arrB, bl, bm, k);
return fd(arrA, al, am, arrB, bl, br, k);
}
}

public static int findKMax(int[] arrA, int[] arrB, int k) {
// 处理零界情况 减少复杂度
if( arrA[arrA.length-1] < arrB[0] ) {
if( k < arrA.length ) return arrA[k];
else return arrB[k-arrA.length];
}
if( arrB[arrB.length-1] < arrA[0] ) {
if( k < arrB.length ) return arrB[k];
else return arrA[k-arrB.length];
}
if( k<arrA.length && arrA[k]<arrB[0] ) return arrA[k];
if( k<arrB.length && arrB[k]<arrA[0] ) return arrB[k];
if( k>arrA.length && arrB[k-arrA.length]>=arrA[arrA.length-1] ) return arrB[k-arrA.length];
if( k>arrB.length && arrA[k-arrB.length]>=arrB[arrB.length-1] ) return arrA[k-arrB.length];

return fd(arrA, 0, arrA.length-1, arrB, 0, arrB.length-1, k);
}
public static void main(String[] args) throws Exception {
int[] arrA = new int[10];
int[] arrB = new int[10];

for(int i = 0; i < 10; i++) {
arrA[i] = i;
arrB[i] = i + 3;
}

// Scanner scanner = new Scanner(System.in);
// while(true) {
// int d = scanner.nextInt();
// System.out.printf("d = %d,  result = %d\n", d, findKMax(arrA, arrB, d));
// }

for(int i = 0; i < 20; i++)
System.out.printf("i = %d,  result = %d\n", i, findKMax(arrA, arrB, i));
}
}

Answer 4

fd函数中
a表示数组a
b表示数组b
l表示左
r表示右
m表示中am对应的就是数组a的中间位子
这样看我的代码也就没那么乱了^_^

Answer 5

启发：在一个有序序列中查找某个值，使用二分查找需要O(lgn)；如果在数组A中找某个值，那个值的位置假设为wa，同样在数组B中找的位置是wb，如果可以办到wa+wb=k，那么算法的时间复杂度就为O(lgm+lgn)了可行性：二分查找在实现上是去中间值进行比较的，这个有点像是指针，底了上升，高了下降；因此在wa+wb=k的等式中wa位置的值相对太高了就可以将wa调底(减去1/2)，wb同样的道理，这样协同的调整是可以得到满足等式wa+wb=k的wa和wb的；所以是可行的设计：
分析情况
1.数组A中所有的数都比数组B中的数小，那么第k大的数就在A的第k位置上或者在B的第k-A.length位置上
2.k小于数组A的长度，同时数组A中前k个数比数组B中的任意数都要小，那么第k大的数就在A的第k位置上
3.k大于数组A的长度，同时数组B中前k-A.length个数都小于等于A中最大的数，那么第k大的数就在A的最后一个位置上
4.k在数组A和数组B交叉的位置上，这是真正需要设计查找的地方查找算法：
感觉用自然语言描述起来比较麻烦，就直接给代码注释一下吧
// 原先的有点错误 这个已经更正过了
// 以下的算法并没有考虑序列中有重复的情况
public static int fd(int[] arrA, int al, int ar, int[] arrB, int bl, int br, int k) {
int am = (ar - al) / 2 + al;
int bm = (br - bl) / 2 + bl;
// am,bm,k都是从0开始计数的 所以比较时am+bm+2,k+1
if( am+bm+2 < k+1 ) { // am+bm+2 < k+1 可以得出k的在arrA[am]之后 或者在arrB[bm]之后
if( arrA[am+1] < arrB[bm+1] ) { // 如果直接比较arrA[am]和arrB[bm]，根本不知道后面的
// 情况，arrA[am]<arrB[bm]时，有可能arrA[am+1]>arrB[bm]
if( ar-am == 1 ) am = ar; // ar前面作为中间位置，但实际B中有比arrA[ar]大的数，所以要回到那位置
return fd(arrA, am, ar, arrB, bl, br, k);
}
if( br-bm == 1 ) bm = br;
return fd(arrA, al, ar, arrB, bm, br, k);
} else if( am+bm+2 == k+1 ) {
if( arrA[am] == arrB[bm] ) return arrA[am];
if( arrA[am] < arrB[bm] ) {
if( bm==0 || arrA[am]>=arrB[bm-1] ) return arrB[bm];
if( arrA[am+1] < arrB[bm] ) return fd(arrA, am, ar, arrB, bl, bm, k);
else return arrB[bm];
}
// arrA[am] > arrB[bm]
if( am==0 || arrA[am-1]<=arrB[bm] ) return arrA[am];
if( arrA[am] > arrB[bm+1] ) return fd(arrA, al, am, arrB, bm, br, k);
else return arrA[am];
} else { // am+bm+2 > k+1
if( arrA[am] < arrB[bm] ) return fd(arrA, al, ar, arrB, bl, bm, k);
return fd(arrA, al, am, arrB, bl, br, k);
}
}