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的位置。
没有评论:
发表评论