V2EX › binux 的所有回复 › 第 116 页 / 共 339 页

@xxlong
https://i.imgur.com/YczTdkk.png
https://gist.github.com/binux/1fc354bfd95836e92f19e3250527b2c9

并没有问题，是可以 AC 的，是算法是可以证明的。
基本思路就是从 An...An-1, An...An-1, An...An-2 找中位数最小的，然后二分为两个数组。
可以证明左边的 B0...Bm 一定大于 Bm...Bn 。

极端情况下（已排序数组），需要反复计算 A0...An, A0...An-1, A0..An-2 的中位数，不过这是可以优化的。复杂度应该是 O(nlogn)

2018-03-28 16:30:29 +08:00

回复了 fov6363 创建的主题 › 程序员 › [面试][算法] 昨天面试碰到了一个算法题,比较有难度,放上来看各位 v 友有没有办法和思路?

来个 O(nlogn) 复杂度的算法

https://gist.github.com/binux/1891d88a3a7e47775f490fc1e32b8fa7

和 42L 结果一致

2018-03-28 13:11:41 +08:00

回复了 fov6363 创建的主题 › 程序员 › [面试][算法] 昨天面试碰到了一个算法题,比较有难度,放上来看各位 v 友有没有办法和思路?

@binux 发现对已排序无效，补一下
第 n 位时，从 n 向 0 找一个分割点，使得右边中位数总小于左边中位数，取右边中位数
第 n-1 位时，从 n-1 向 0 找一个分割点，使得右边中位数总小于左边中位数，取右边中位数
以此类推

2018-03-28 12:49:27 +08:00

回复了 fov6363 创建的主题 › 程序员 › [面试][算法] 昨天面试碰到了一个算法题,比较有难度,放上来看各位 v 友有没有办法和思路?

@binux 继续我那个思路
第 n 位修改为 [a0...an] 的中位数。（即所有位叠加 1，能得到的最小 △）
第 n-1 位修改为 [a0...a(n-1)] 的中位数与第 n 位中大的。（即 0...n-1 位叠加 1，能得到的最小 △）
第 n-2 位修改为 [a0...a(n-2)] 的中位数与第 n-1 位中大的。
以此类推

2018-03-28 11:37:30 +08:00

回复了 fov6363 创建的主题 › 程序员 › [面试][算法] 昨天面试碰到了一个算法题,比较有难度,放上来看各位 v 友有没有办法和思路?

@vegito2002 然后再贪心什么的优化呗。我只是给个思路

2018-03-28 11:29:05 +08:00

回复了 fov6363 创建的主题 › 程序员 › [面试][算法] 昨天面试碰到了一个算法题,比较有难度,放上来看各位 v 友有没有办法和思路?

这个单链表感觉完全没有用啊，用个数组不是一样的吗？

从最小有效列表，[111...1] 开始
将 0 至 n1 位 +1，使得 △ 变小。得到列表 [2221...1]
将 0 至 n2 (n2<n1) 位 +1，使得 △ 变小。得到列表 [33..322..2111..1]
直到 △ 不再变小。

2018-03-26 13:29:59 +08:00

回复了 gaocc 创建的主题 › 问与答 › 老忘记喝自己泡的豆浆，茶，咖啡等饮料怎么办，隔夜只能倒掉。

没有必要就喝白开水就好了啊，如果你不饿，不困，你根本不需要喝这些东西，如果你饿了，困了，自然不会忘记。

2018-03-26 11:52:24 +08:00

回复了 pke 创建的主题 › 奇思妙想 › 脑洞，换个思路买房~

没钱买房的，需要贷款的，你确定能集够资拍下土地？

2018-03-26 10:00:45 +08:00

回复了 gbin 创建的主题 › 算法 › 2018026 今日算法

我被题目误导了，因为你这输出不唯一啊，但是没要求给出"所有"子数组啊

2018-03-26 09:52:08 +08:00

回复了 gbin 创建的主题 › 算法 › 2018026 今日算法

@hanzichi 不过经你这么一说，好像没有规定连续的个数啊。。尴尬

2018-03-26 09:50:41 +08:00

回复了 gbin 创建的主题 › 算法 › 2018026 今日算法

@hanzichi 反正数组有序，和它左右两边相加也是有序的，二分就好了嘛。

2018-03-26 09:28:31 +08:00

回复了 gbin 创建的主题 › 算法 › 2018026 今日算法

@gbin 超偏门的算法。

2018-03-26 09:23:52 +08:00

回复了 gbin 创建的主题 › 算法 › 2018026 今日算法

@binux 哦，确实可以 O(logn) 的。不过还是挺无趣的。

1 ... 112 113 114 115 116 117 118 119 120 121 ... 339

❮

❯