2015年2月14日星期六

LintCode Merge Two Sorted Arraylist

public static ArrayList<Integer> mergeSortedArray(ArrayList<Integer> A, ArrayList<Integer> B) {
               //null check
if (A == null && B == null) {
return new ArrayList<Integer>(Arrays.asList(-1));
} else if (A == null && B != null) {
return B;
} else if (A != null && B == null) {
return A;
}
             
               // initial a new array
ArrayList<Integer> result = new ArrayList<Integer>();

               
for (int i = 0,j=0; i <A.size() || j <B.size() ;) {

if (i < A.size() && j > B.size()-1) {
result.add(A.get(i));i++;continue;
} else if (i > A.size()-1 && j < B.size()) {
result.add(B.get(j));j++;continue;
}

if (A.get(i) < B.get(j)) {
result.add(A.get(i));i++;
} else if (A.get(i) > B.get(j)) {
result.add(B.get(j)); j++;
} else if (A.get(i) == B.get(j)) {
result.add(A.get(i));
result.add(B.get(j));
i++;
j++;
}
}

return result;
    }

一开始不明白的点:
(1)  i <A.size() || j <B.size() 应该选OR 做,如果是选择&& 的话,T &F return F 所以就会跳出循环,这里应该使用OR, T V F= return True 只有在F V F 的时候才return false (boolean 值)
(2) 结束 语句:

if (i < A.size() && j > B.size()-1) {
result.add(A.get(i));i++;continue;
} else if (i > A.size()-1 && j < B.size()) {
result.add(B.get(j));j++;continue;
}
这句是为了判断当A和B长度不一致的时候应该怎样处理, 如果A 比B 长,那么我们就填入B的元素。如果B比A长,那么我们就应该填入B剩下的元素。
(3) break 和continue 均是跳出循环的,例如break ,就直接return 了,continue 就直接回到for loop 或者while.
(4) 一开始只想用一个指针,就是result 的指针。但是在比较当中,最好用两个指针。
(5) 这个和reomove duplicate from sorted array 都是很相似的做法,都是使用两个指针,并且都是比较i和j的位置。

没有评论:

发表评论