ARTS 第 4 周

每周一道算法、点评一篇英文技术文章、学习一个技术技巧、分享一个技术观点和思路

Algorithm

题目:Median of Two Sorted Arrays

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)).

思路 1

将两个数组中的值按从小到大排序,但是不用把所有数都排完,只需要排到中位数就行。

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
30
31
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int total_length = nums1.length + nums2.length;
int median = total_length / 2;
int i1 = 0, i2 = 0;
int[] result = new int[median + 1];
for (int j = 0; j <= median; j++) {
if (i1 >= nums1.length) {
result[j] = nums2[i2++];
continue;
}

if (i2 >= nums2.length) {
result[j] = nums1[i1++];
continue;
}

if (nums1[i1] >= nums2[i2]) {
result[j] = nums2[i2++];
} else {
result[j] = nums1[i1++];
}
}
if (total_length % 2 == 0) {
int i3 = result[result.length - 1] + result[result.length - 2];
return i3 / 2.0;
} else {
return result[result.length - 1];
}
}
}

思路 2

在统计学上中位数是将一组分成两个相等长度的子集,一个子集总是大于另一个子集。

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
30
31
32
33
34
35
36
class Solution {
public double findMedianSortedArrays(int[] A, int[] B) {
int m = A.length;
int n = B.length;
if (m > n) { // to ensure m<=n
int[] temp = A; A = B; B = temp;
int tmp = m; m = n; n = tmp;
}
int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;
while (iMin <= iMax) {
int i = (iMin + iMax) / 2;
int j = halfLen - i;
if (i < iMax && B[j-1] > A[i]){
iMin = iMin + 1; // i is too small
}
else if (i > iMin && A[i-1] > B[j]) {
iMax = iMax - 1; // i is too big
}
else { // i is perfect
int maxLeft = 0;
if (i == 0) { maxLeft = B[j-1]; }
else if (j == 0) { maxLeft = A[i-1]; }
else { maxLeft = Math.max(A[i-1], B[j-1]); }
if ( (m + n) % 2 == 1 ) { return maxLeft; }

int minRight = 0;
if (i == m) { minRight = B[j]; }
else if (j == n) { minRight = A[i]; }
else { minRight = Math.min(B[j], A[i]); }

return (maxLeft + minRight) / 2.0;
}
}
return 0.0;
}
}

Review & Tip

这周依旧是Pro Git 第二版,主要是第 6 ~ 10 章。

以前重来没这么完整的读过 Git 的文档,这次在里面学到了很多小技巧。比如 rebase 除了用来合并,还可以重写历史,合并提交记录,这样的话就可以把很碎的提交合并为一个大的提交。还是高级合并Rerere钩子

最后讲了 Git 内部原理,第一次知道 Git 命令分为“高层(porcelain)”命令和“底层(plumbing)”命令,所谓的高层命令都是底层命令的组合。对 Git 的底层存储有了一点了解,知道了 Git 各个对象的作用以及存储的位置。强烈推荐看。

Share

这周分享的不是技术观点,而是假疫苗事件。

真的是心凉,为了赚钱真的是什么都敢干。美国强生痱子粉致癌 22 人获配 47 亿美元,而 18万已注入病人体中假疫苗,处罚 300 万。

呵呵。

违法成本真的是低。也难怪这些人胆大包天,毫无人性。

无(f)话(u)可(c)说(k),一句话努力赚钱。

(完)