l******i
发帖数: 880 | 1 今天面试遇到一个题，输入是一个排好序的整数数组，要求对数组的每个元素apply
function = a*x^2 + b*x + c，其实相当于代入一个二项式，然后对结果进行有序输出
。要求O(n).
普通排序肯定达不到O(n), 问题是怎么利用这个二项式的特点来达到呢？ |
s***n
发帖数: 459 | 2 既然输入是拍好序的，那就先求二项式的顶点，半边是单调下降，另半边单调上升，
两边的输出都是排好序的，最后再merge起来。 |
M**a
发帖数: 25 | 3 LeetCode 360. Sort Transformed Array |
s***n
发帖数: 459 | 4 哈哈，不刷题能行吗？！
【在 M**a 的大作中提到】
: LeetCode 360. Sort Transformed Array
|
l******i
发帖数: 880 | 5 只做了200道题。。。哎。。。
【在 s***n 的大作中提到】
: 哈哈，不刷题能行吗？！
|
s***n
发帖数: 459 | 6 提醒的好！算顶点是脱裤子放屁，一路求下去不就看到拐点了嘛
【在 l******i 的大作中提到】
: 只做了200道题。。。哎。。。
|
s***n
发帖数: 459 | 7 借机给我老的刷题班打个广告吧！搜“刷题就得快糙猛”，投简历预审 ^_^ |
g****y
发帖数: 2810 | 8 所以必须做完，一题也不能少
：只做了200道题。。。哎。。。
： |
s***n
发帖数: 459 | 9 哈哈！我的理解是路子正的题必须做完，有些太拐外抹角的，太数学化的，太头脑风暴
的，还有太繁琐就靠测试case来fail人的，不必纠结。
【在 g****y 的大作中提到】
: 所以必须做完，一题也不能少
:
: ：只做了200道题。。。哎。。。
: ：
|
g****y
发帖数: 2810 | 10 所以这题你得挂
：哈哈！我的理解是路子正的题必须做完，有些太拐外抹角的，太数学化的，太头脑风
暴的，还有太繁琐就靠测试case来fail人的，不必纠结。
：【 在 garphy (喜欢猫) 的大作中提到: 】 |
s******m
发帖数: 7 | |
s******m
发帖数: 7 | |
