Algorithm
LeetCode算法题
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
You may assume nums1 and nums2 cannot be both empty.
Example1:
nums1 = [1, 3] nums2 = [2]
The median is 2.0
Example2:
nums1 = [1, 2] nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
Java 程序实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int len1 = nums1.length;
int len2 = nums2.length;
int left = (len1 + len2 + 1) / 2;
int right = (len1 + len2 + 2) / 2;
return (findK(nums1, len1, 0, nums2, len2, 0, left) + findK(nums1, len1, 0, nums2, len2, 0, right)) * 0.5;
}
private int findK(int[] nums1, int len1, int offset1, int[] nums2, int len2, int offset2, int k) {
if (k == 1) {
return Math.min(offset1 < len1 ? nums1[offset1] : Integer.MAX_VALUE, offset2 < len2 ? nums2[offset2] : Integer.MAX_VALUE);
}
int pivot = k / 2;
int p1 = len1 < offset1 + pivot ? Integer.MAX_VALUE : nums1[offset1 + pivot - 1];
int p2 = len2 < offset2 + pivot ? Integer.MAX_VALUE : nums2[offset2 + pivot - 1];
k = k - pivot;
if (p1 < p2 ) {
return findK(nums1, len1, offset1 + pivot, nums2, len2, offset2, k);
} else {
return findK(nums1, len1, offset1, nums2, len2, offset2 + pivot, k);
}
}
}
Review
Efficient query evaluation using a two-level retrieval process
WAND(Weak AND)算法，是上下文定向广告和内容推荐产品中非常实用的快速检索算法。其解决相关性搜索的基本思路是在检索阶段就引入某种评价函数，并以此函数的评价结果决定返回哪些候选。
Tip
架构师需要有全局思维，而不是事不关己高高挂起的听之任之的态度。
