-
第 11 樓 / webdriver
- 時間: 2014-9-28 01:05
-
-
第 12 樓 / webdriver
- 時間: 2014-9-28 01:10
-
-
第 13 樓 / webdriver
- 時間: 2014-9-28 01:11
-
第 14 樓 / webdriver
- 時間: 2014-9-28 01:11
-
第 15 樓 / webdriver
- 時間: 2014-9-28 01:12算法問題推薦解法來了...
1. O(m+n)
2. O(log(m+n))
3. O(logm + logn)
解法(Java)
代碼:
public class MedianOfTwoSortedArrays {
public double findMedianSortedArrays(int A[], int B[]) {
int m = A.length;
int n = B.length;
int k = m + n;
if (k % 2 != 0) {
return findKth(A, 0, B, 0, k / 2 + 1);
} else {
return (findKth(A, 0, B, 0, k / 2) + findKth(A, 0, B, 0, k / 2 + 1)) / 2.0;
}
}
private double findKth(int A[], int a, int B[], int b, int k) {
if (A.length - a > B.length - b) {
return findKth(B, b, A, a, k);
}
if (a >= A.length) {
return B[b + k - 1];
}
if (k == 1) {
return Math.min(A[a], B[b]);
}
int midA = Math.min(k / 2, A.length - a);
int midB = k - midA;
if (A[a + midA - 1] < B[b + midB - 1]) {
return findKth(A, a + midA, B, b, k - midA);
} else if (A[a + midA - 1] > B[b + midB - 1]) {
return findKth(A, a, B, b + midB, k - midB);
} else {
return A[a + midA - 1];
}
}
}
-
第 16 樓 / webdriver
- 時間: 2014-9-28 01:24
-
第 17 樓 / webdriver
- 時間: 2014-9-28 01:25算法問題推薦解法來了...
1. Sort in ascending order of 'start'.
2. Traverse the 'intervals', merge or push...
解法(Java)
代碼: import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
public class MergeIntervals {
public class IntervalCmp implements Comparator<Interval> {
@Override
public int compare(Interval i1, Interval i2) {
if (i1.start < i2.start) return -1;
if (i1.start == i2.start && i1.end <= i2.end) return -1;
return 1;
}
}
public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
ArrayList<Interval> ret = new ArrayList<Interval>();
if (intervals.size() == 0) return ret;
Interval[] arr = new Interval[intervals.size()];
intervals.toArray(arr);
Arrays.sort(arr, new IntervalCmp());
int start = arr[0].start;
int end = arr[0].end;
for (int i = 0; i < arr.length; i++) {
if (arr[i].start <= end) {
end = Math.max(end, arr[i].end);
} else {
ret.add(new Interval(start, end));
start = arr[i].start;
end = arr[i].end;
}
}
ret.add(new Interval(start, end));
return ret;
}
} -
第 18 樓 / webdriver
- 時間: 2014-9-28 01:26
-
第 19 樓 / webdriver
- 時間: 2014-9-28 01:26算法問題推薦解法來了...
Find the smallest list-head first using minimum-heap(lgk).
complexity: O(NlgK)
解法(Java)
代碼:
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
public class MergekSortedLists {
public ListNode mergeKLists(ArrayList<ListNode> lists) {
if (lists == null || lists.isEmpty())
return null;
Comparator<ListNode> comp = new Comparator<ListNode>() {
public int compare(ListNode o1, ListNode o2) {
if (o1.val < o2.val)
return -1;
if (o1.val > o2.val)
return 1;
return 0;
}
};
PriorityQueue<ListNode> heap = new PriorityQueue<ListNode>(
lists.size(), comp);
for (ListNode node : lists) {
if (node != null)
heap.add(node);
}
ListNode head = null, cur = null;
while (!heap.isEmpty()) {
if (head == null) {
head = heap.poll();
cur = head;
} else {
cur.next = heap.poll();
cur = cur.next;
}
if (cur.next != null)
heap.add(cur.next);
}
return head;
}
} -
第 20 樓 / webdriver
- 時間: 2014-9-28 01:27