java算法的问题

Question

java算法的问题内存里有二个装着同样对象已经有序的集合
一个装着有100多万条有序数据
一个装着有10多万条有序数据
请问怎么高效的把这10万条数据有序的插入到那100多万条数据中？跪求此解决方案

Answer 1

这个其实内存1G都不要嘛。。一个数据也就几十Byte。。
二分插入？就是归并的那个么？这个效率比较低。。

Answer 2

记M=1000000 N=100000
二分查找插入的时间复杂度为
N*log2(M)
大概200万左右的时间复杂度
两个集合都有序了，直接从集合的头开始归并么
时间复杂度大概为
100万左右
稍微大于100万，
因为这10万也要从头数到尾，但不用做循环
所以归并要快些

Answer 3

支持这个
2分没必要 
100000 * lg(1000000) >> 100000 + 1000000
用双指针归并比较快

Answer 4

这里给个int 数组的归并
对象数组的话自己写比较规则public class Test { public static void main(String[] args) {
int[] arr1 = {1,3,4,5,9};
int[] arr2 = {2,6,7};
int[] arr = mergeTest(arr1, arr2);
for (int i = 0; i < arr.length; i++) {
System.out.printf("%d ",arr[i]);
}
} public static int[] mergeTest(int[] arr1, int[] arr2){
int[] arr = new int[arr1.length + arr2.length];
int index1 = 0;
int index2 = 0;
int index = 0;
while(index1 < arr1.length && index2 < arr2.length){
if(arr1[index1] <= arr2[index2]){
arr[index++] = arr1[index1++];
}
else{
arr[index++] = arr2[index2++];
}
}
if(index1 < arr1.length){
arr[index++] = arr1[index1++];
}
if(index2 < arr2.length){
arr[index++] = arr2[index2++];
}
return arr;
}
}

Answer 5

/**
 * 归并操作(merge)，也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。
算法描述
归并操作的工作原理如下：
1.申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2.设定两个指针，最初位置分别为两个已经排序序列的起始位置
3.比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4.重复步骤3直到某一指针达到序列尾
5.将另一序列剩下的所有元素直接复制到合并序列尾
 * @param arrOne
 * @param arrTwo
 * @return
 */
private static int[] mergeSort(int[] arrOne, int[] arrTwo) {
int[] res = new int[arrOne.length + arrTwo.length];
int index = 0, temp;
int i = 0, j = 0;
for (; i < arrOne.length && j < arrTwo.length;) {
if (arrOne[i] > arrTwo[j]) {
temp = arrTwo[j];
j++;
} else {
temp = arrOne[i];
i++;
}
res[index++] = temp;
}
//处理没有比较的数据添加结果数据后面
if (i > j) {
for (; j < i; j++) {
res[i + j] = arrOne[j];
}
} else {
for (; i < j; i++) {
res[i + j] = arrOne[i];
}
}
return res;
}
我这个比较简单，不知道时候你那么大的数据不。

Answer 6

我就是这样的思路，不过用的java的集合类，用这集合的效率应该比数组低吧

Answer 7

什么集合类？ArrayList就不会低到哪里去

Answer 8

Java类库有时候确实不咋样
就拿 string 的中的 indexof 那个方法来说
类库用的是 O(n^2)的算法
但其实是能做到 O(n) 的
类库这么写可能是有别的方面的考虑吧
总体来说类库还可以
楼主如果追求个人对程序的控制的话 可以自己写写有针对性的算法
毕竟通用的处于各方面的考虑 有时候效率并不高

Answer 9

我在 8 楼的代码有点问题 if(index1 < arr1.length){
            arr[index++] = arr1[index1++];
        }
        if(index2 < arr2.length){
            arr[index++] = arr2[index2++];
        }
这里的两个 if 都要改成 while ，BS 自己

Answer 10

不知道有没有重复的？如果没有重复的就用 TreeSet 吧，红黑树的数据结构，查找、插入、删除都有不错的效率。