Leetcode - Median of Two Sorted Arrays

对这题想到一个方法,既然是两个 Sorted Arrays, 用 Merge Sort 类似的归并方法组合两个数组就可以了, 根据总长度的奇偶抽取第 N 大的数值出来就完成啦。但这样做的话运行时间是 O(m+n / 2), 题目要求 O(log(m+n))

第一个想法就是二分, 参考了几个博文之后, 先准备一个 Kth 函数用于寻找两个 sorted array 的第 K 小的数, 然后中位数就很容易了, 反而一开始追求二分中位数似乎会有不少 corner cases

那先把问题换成两个有序数组的第 K 小的数值

有以下步骤

  • 有序 vector v1 和 v2, 求第 K 小
  • 二分思想是每次从 v1 和 v2 排除一半的可选元素
  • 有 x, y > 0 && x + y == k,
  • x, y 的取值也是有讲究, x = len(v1) / (len(v1) + len(v2)) * k, 这个意思是 len(v1) 占总 size 的百分比, 再乘以 k 的话就可以确保 x 的取值不会超出 v1 的数组范围, 这里简化了, 实际代码需要注意一些边界问题
  • 如果 v1[x] < v2[y], 则 v1[0 .. x] 的元素都不可能是第 K 小, 他们都肯定比第 K 的数值要小了, 我们则可以排除掉这些数值,
  • v1[x] > v2[y] 的话都是同样的思想
  • 调整 v1, v2 的长度, 下表值, k 的值等, 然后重复这些取值然后比较的步骤,
  • 调整完 size 和 下标后, 检查一下 k 是否下降到 1, 第 1 小的值是 min(v1[0], v2[0]), 还有如果其中一个 vector 的 size 下降到 0, 那可以直接返回另一个 vector 的第 k 个值
  • 如果是 v1[x] == v2[y] 的话, x + y == k, v1[x] == v2[y], 那这个数值已经是第 K 小了, 这里是一个 base case

大家可以 Leetcode 测试一下自己的代码 https://leetcode.com/problems/median-of-two-sorted-arrays/

下面是我提交的代码

Read More

打印蛇形数组

唉, 不熟练连这样的题都不会入手。。

题目大概是这样 http://icpc.ahu.edu.cn/OJ/ContestProblem.aspx?cid=16&id=410
参考了 http://www.cnblogs.com/kaima/p/4773908.html

外部的 while 循环检查 number 是否到 N * N, 如果 N 为偶数则可以在这里停下, (最后四个位置刚好填完)
里面第一个 if 检查奇数 N 的情况(会填充剩下一个位置)

然后开始填充数组, 调节 x y 的坐标值填充一圈蛇形, 一圈后 x y 回归原点
缩小 size 变量
x+1, y+1 跳入内圈重复以上步骤又填充一圈, 直至跳出 while 循环

x y 走向

代码如下

Read More

韩剧《未生》

未生、完生

一年内断断续续的看完了这部剧, 第一次看到『未生』这词完全想不到什么意思, 其实这是个韩国的围棋术语。『未生』对应『完生』, 完生其实就是双眼活棋, 未生就借喻职场新人了。

不同于某些套题作文剧, 是有共鸣在, 这励志鸡汤熬得不错。

《未生》剧照