L***Q
发帖数: 508 | 1 据称是facebook面试题，大意如下：
给一个int array，找出最长的递增的contiguous subarray。算法worst case是O（n）
，如何提高average 的效率。
算法我想了一个：给定array A，从左到右扫描。最初起点为A[0]找出递增的
contiguous subarray，假设结束与A[k-1]。然后以A[k]为起点扫描下一个递增的
contiguous subarray。worse case为O(n)。
关于如何提高average效率，我想到2个策略：
1. 如果剩下未扫描部分小于当前最长的递增的contiguous subarray，那剩下不用扫描
了；
2. 假设当前最长递增的contiguous subarray长度为k，接下来的扫描起点是A[i]，那
么首先比较A[i+k]和A[i+k+1]，如果A[i+k]大于A[i+k+1]，那么跳过A[i]到A[i+k]，以
A[i+k+1]作为扫描起点。因为如果A[i+k]大于A[i+k+1]，从A[i]开始的递增的
contiguous subarray长度最多为k，那可以不用扫描。
第二个策略有一个变形时当A[i+k-1] < A[i+k] < A[i+k+1]时以A[i]为扫描起点。
不知道各位还有没有其他提高average 效率的策略呢？ |
f***g
发帖数: 214 | 2 再贡献一个想法：
第二策略，除了判断
if( A[i+k] > A[i+k+1] ) 跳到 A[i+k+1]
还有
if( A[i+k] - A[i] < k ) 同样跳过
（这里面假设是严格单调递增） |
y******5
发帖数: 43 | 3 不能这样跳吧。A[i+1]到A[i+k]可能符合递增。
【在 f***g 的大作中提到】
: 再贡献一个想法：
: 第二策略，除了判断
: if( A[i+k] > A[i+k+1] ) 跳到 A[i+k+1]
: 还有
: if( A[i+k] - A[i] < k ) 同样跳过
: （这里面假设是严格单调递增）
|
f***g
发帖数: 214 | 4 给个例子？
【在 y******5 的大作中提到】
: 不能这样跳吧。A[i+1]到A[i+k]可能符合递增。
|
y******5
发帖数: 43 | 5 不知道我理解得是否准确。 A[i+1]可以比A[i]小啊，所以不能根据A[i+k] - A[i] < k
就直接跳
到A[i+k]吧。
【在 f***g 的大作中提到】
: 给个例子？
|
L***Q
发帖数: 508 | 6 或许是我题目表述不清楚。找到的subarray是连续的，并且递增的。所以A[i+1] < A{i
]的话这个subarray就不符合条件。
我觉得fzblg提供的策略是对的。如果是严格递增，那通过判断A[k+i] - A[i] > k决定
是否跳过A[i]是对的。如果题目没说是严格递增，应该不能这么判断。
k
【在 y******5 的大作中提到】
: 不知道我理解得是否准确。 A[i+1]可以比A[i]小啊，所以不能根据A[i+k] - A[i] < k
: 就直接跳
: 到A[i+k]吧。
|
i**********e
发帖数: 1145 | |
s*****y
发帖数: 897 | 8 Ye. I remember this post I read last year. The most niu method.
【在 i**********e 的大作中提到】
: 这个板上讨论过，看看...
: http://www.mitbbs.com/article_t/JobHunting/31724411.html
|
j*****u
发帖数: 1133 | 9 depends on CPU cache line size and current_max_len, in real life jumping may
not be more efficient than liner scanning since it could introduce a lots o
f cache miss/reloading.
【在 s*****y 的大作中提到】
: Ye. I remember this post I read last year. The most niu method.
|
