说几个 leetcode 上看似简单却又非常困难的问题

[Goldilocks]

1. Merge two sorted array

https://leetcode.com/problems/merge-sorted-array/

Q1: 算法复杂度的下界是多少？如何算出来的？

Q2: 常规两个指针线性的往前走谁都会写，但是如何 binary search 加速它?aka. binary search merge

1. Shuffle the Array

https://leetcode.com/problems/shuffle-the-array

如何 inplace 的在线性的时间复杂度完成它？如何证明你的算法是对的？

这个题其实是在考察你对抽象代数的理解。因为这个所谓的 shuffle 就是 permutation 。permutation group 可以被分解成 orbits 。然后你就只需要一个 orbit 、一个 orbit 的去处理就行了。但是如何找出这些 orbits 呢？能不能同时处理多个 orbits 呢？

1. Running Sum of 1d Array https://leetcode.com/problems/running-sum-of-1d-array/

看起来很简单是吧？ 如果是浮点数怎么办？如何利用 binary tree 最小化计算误差？

1. find the median number of an array

《算法导论》花了很大的篇幅去讲这个问题，没有认真学过的人肯定是不懂的，尤其是那个最坏情况为线性时间的选择算法，为什么《算法导论》上是每 5 个一组但是 TAOCP 上的描述是 7 个一组？除了这些 textbook 算法外，你还有什么 idea ？比如如何用概率论和统计学知识开发一个期望线性的随机化算法？

一味的刷题是没有用的，对于找到这些 easy 问题的答案没有帮助。

同时这也回答了另一个问题：面试的时候怎么判断面试者是不是速成的？ 很简单，认真学过算法的科班学生，多少会对这些问题有些 sense 。而速成的只能靠刷题，刷不出这些 idea 。他甚至不知道 binary search merge 的存在。但是如果他但凡看过 MIT 、普林斯顿或任何一个名校的算法公开课，他都会知道 binary merge/median find 不是那么的简单的问题。

[Girlphobia]

坚定了我有空一定要把垫显示器的《算法导论》拿出来仔细看一遍的决心。

[daozhihun]

如果你只是想要知道别人是否认真学过算法，直接出个题目考网络流算法、A*搜索剪枝不是更好吗？
我觉得面试的目的是考察对方的思维能力，而不是单纯地判断他是否看过哪些公开课什么的。

[lights]

这是要造火箭还是造无人汽车啊

[GtDzx]

binary search merge 是啥？ 怎么加速的？ 还真没听说过...

[SingeeKing]

@GtDzx 简单说就是楼主列举的第一题的 O(logN) 解法

[GtDzx]

@SingeeKing 这题至少要把 2 个数组遍历一遍吧，还能 O(logN)? 讲讲怎么做？

[levelworm]

@Girlphobia 当初看了几页就放弃了，感觉还是红色那本舒服一点。不过我觉得还是从项目中寻找问题比较好。。。否则看完也忘记了。

[Sevenskey]

@SingeeKing 呃，这题最优解是 o(m+n)啦，没有 log 的解法

[Goldilocks]

@Sevenskey 你能证明它至少需要 o(m+n)次比较吗？不能啊。

[Sevenskey]

@Goldilocks 。。那你能证明它在某种算法下最多只需要 log(m+n)的比较吗

[e583409]

我理解 刷题的目很多人没有搞懂 为了数量 而不是质量 为了刷题而刷题
这个是我的答案 https://github.com/xrfinbupt/leetcode_java

[Goldilocks]

二路归并，其实是在问，如果你把 m 个排好序的数字插入到另外 n 个排好序的数组中，那么那 m 个数的 position 有多少种可能性？
然后再回过头来，基于比较的排序，为什么下界是 nlogn ？
把这两个问题的答案结合起来，就可以得知二路归并的算法复杂度下界。

[Goldilocks]

举个例子，当 m 等于 1，那么显然共有 n+1 种可能性。用 log （ n+1 ）次比较就能解决问题

[Sevenskey]

@Goldilocks 啊这，那你这复杂度不是 log(n+m)而是 mlogn 啊。。另外大 o 记号是表示上界的

[Goldilocks]

@Sevenskey 我自始自终就没说过 log(n+m)啊。而且也不是 mlogn 。我甚至连大 O 都没有提过。对于这样的简单问题，大 O 太粗糙了。大 O 是上界，所以要看谁能找到更精确的上界中的下界。

[e583409]

@e583409 不知不觉 用半年 刷了 178 道题