算法面试题——两个有序数组，将一个数组放入另一个空间很大的数组，要求合并之后依然有序，时间复杂度要求最小，不使用额外的数
昨天接到了一个电话面试，要求写一到算法题。我才疏学浅，用基本的数组实现的。往大鸟们给些建议。 这个版本有点问题，没有用上折半查找函数，直接用的是数组循环插入。经过修改后，用linkedlist进行链表插入，减少时间复杂度。
public class TwoArraySort {
public static void main(String[] args) {
int a[];
a = new int[20];
a[0] = 1;
a[1] = 2;
a[2] = 4;
a[3] = 7;
a[4] = 10;
a[5] = 30;
int b[] = {3,12,13,15};
Insert(a,b);
for(int i =0 ; i<a.length;i++){
System.out.print(a[i]);
}
}
public static void Insert(int[] a,int[] b){
int i;
int j;
int postion1 = 0;
int postion2;
int num;
for(i = 0;i<b.length;i++){
num = b[i];
postion2 = halfSeacrh(a,num,postion1);
postion1 = postion2;
for (j = arrayLength(a) ;j > 0&& num < a[j-1]; j--) {
a[j]=a[j-1];
}
a[j]=num;
}
}
public static int halfSeacrh(int[] a,int number, int postion1 ){
int startPostion=postion1;
int endPostion=arrayLength(a)-1;
int postion=(startPostion+endPostion)/2;
while(startPostion<endPostion){
if(a[postion] == number)
return postion;
else if(a[postion]<number){
startPostion=postion+1;
}
else if(a[postion]>number){
endPostion=postion-1;
}
postion=(startPostion+endPostion)/2;
}
return postion;
}
public static int arrayLength(int[] a){
int count = 0;
for(int i = 0 ; i <a.length;i++){
if(a[i] != 0)
count++;
}
return count;
}
}
运用linkedlist
import java.util.Iterator;
import java.util.LinkedList;
public class TwoArraySort {
public static void main(String[] args) {
int a[];
a = new int[20];
a[0] = 1;
a[1] = 2;
a[2] = 4;
a[3] = 7;
a[4] = 10;
a[5] = 30;
int b[] = {3,15};
LinkedList<Integer> c = new LinkedList<Integer>();
c.add(1);
c.add(2);
c.add(10);
Insert(c,b);
Iterator i = c.iterator();
while(i.hasNext()){
System.out.print(i.next());
}
/*
for(int i =0 ; i<a.length;i++){
System.out.print(a[i]);
}
*/
}
public static void Insert(LinkedList<Integer> c,int[] b){
int i;
int j;
int postion1 = 0;
int postion2;
int num;
for(i = 0;i<b.length;i++){
num = b[i];
Integer[] d = new Integer[20];
d = c.toArray(d);
postion2 = halfSeacrh(d,num,postion1);
postion1 = postion2;
System.out.println(postion1);
c.add(postion1 , num);
/*
for (j = arrayLength(a) ;j > 0&& num < a[j-1]; j--) {
a[j]=a[j-1];
}
a[j]=num;
*/
}
}
public static int halfSeacrh(Integer[] a,int number, int postion1 ){
int startPostion=postion1;
int endPostion=arrayLength(a)-1;
int postion=(startPostion+endPostion)/2;
while(startPostion<endPostion){
if(a[postion] == number)
return postion;
else if(a[postion]<number){
startPostion=postion+1;
}
else if(a[postion]>number){
endPostion=postion-1;
}
postion=(startPostion+endPostion)/2;
}
if(a[postion] < number)
return postion + 1 ;
else
return postion;
}
public static int arrayLength(Integer[] v){
int count = 0;
for(int i = 0 ; i <v.length;i++){
if(v[i] != null)
count++;
}
return count;
