JobHunting版 - Find(i,j) in array A to max (j - i) with Aj>Ai |
|---|
|
|
|
|
|
|
k***t
发帖数: 276 | 1 网上看到的真题。自己写了一个答案，还算简洁，但对时间复杂度和不满意。
抛砖引玉吧。哪位来个O(n)的解？
boolean maxji (int a[], int N, int *resi, int *resj) {
int i, j, previ, maxdist, maxi;
if (!a || (N < 2) || !resi || !resj) return FALSE;
j = N-1;
while((a[j] <= a[0]) && (j != 0)) --j;
previ = 0; maxi = 0; maxdist = j - 0;
for (i = 1; i < (N-maxdist-1); ++i) {
if (a[i] >= a[previ]) continue;
previ = i; j = N-1;
while((a[j] <= a[i]) && (j != i)) --j;
if ((j - i) > maxdist) {
maxi = i; maxdist = j - i;
}
}
*resi = maxi; *resj = maxi + maxdist;
return TRUE;
} | B******5
发帖数: 4676 | 2 呃，我被问过max (Aj - Ai) with j > i
这个第一次见。。。 | s******n
发帖数: 226 | 3 维护一个stack，存当前最小，一次pop就搞定了，O（n） | d****n
发帖数: 233 | 4 LIS ?
【在 k***t 的大作中提到】
: 网上看到的真题。自己写了一个答案，还算简洁，但对时间复杂度和不满意。
: 抛砖引玉吧。哪位来个O(n)的解？
: boolean maxji (int a[], int N, int *resi, int *resj) {
: int i, j, previ, maxdist, maxi;
: if (!a || (N < 2) || !resi || !resj) return FALSE;
: j = N-1;
: while((a[j] <= a[0]) && (j != 0)) --j;
: previ = 0; maxi = 0; maxdist = j - 0;
: for (i = 1; i < (N-maxdist-1); ++i) {
: if (a[i] >= a[previ]) continue;
| f*******t
发帖数: 7549 | | a*****n
发帖数: 158 | 6 能不能讲解一下算法，代码不容易看。。。我能想到最坏O(nlgn)，有点想LIS算法。O(
n)好象不太可能 | a*****n
发帖数: 158 | 7 不能用stack吧，所有的最小值得存起来，留给下次比较。
【在 s******n 的大作中提到】
: 维护一个stack，存当前最小，一次pop就搞定了，O（n）
| A**u
发帖数: 2458 | 8 http://www.leetcode.com/2011/05/a-distance-maximizing-problem.h
看1337大牛
O(
【在 a*****n 的大作中提到】
: 能不能讲解一下算法，代码不容易看。。。我能想到最坏O(nlgn)，有点想LIS算法。O(
: n)好象不太可能
| k***t
发帖数: 276 | 9 同时在另一头（右端）把最大值也存起来，用于下次比较时跳跃一些元素。
【在 a*****n 的大作中提到】
: 不能用stack吧，所有的最小值得存起来，留给下次比较。
| b*******y
发帖数: 232 | 10 恩，以前看到过，不过这个算法真的是O(n)的么？
如果预处理的potential starting point的个数跟n可比呢？
【在 A**u 的大作中提到】
: http://www.leetcode.com/2011/05/a-distance-maximizing-problem.h
: 看1337大牛
:
: O(
| | | A**u
发帖数: 2458 | 11 当然是O(N)的
http://www.mitbbs.com/article_t/JobHunting/31875095.html
这里有 darksteel 详解
【在 b*******y 的大作中提到】
: 恩，以前看到过，不过这个算法真的是O(n)的么？
: 如果预处理的potential starting point的个数跟n可比呢？
| n*******w
发帖数: 687 | 12 1337那题没时间写完吧。
最后那个O(n)的算法并不是O(n)。反例比如，worst case是逆序数组，要O(n^2)。
这题看过几个网站给的O(n)解法，包括用stack记录最大最小，分段等等，都不是O(n)
解甚至有些是错的。
【在 A**u 的大作中提到】
: http://www.leetcode.com/2011/05/a-distance-maximizing-problem.h
: 看1337大牛
:
: O(
| b*******y
发帖数: 232 | 13 ic
好像是有两个loop，但数学证明还是O(n)的，是吧？
【在 A**u 的大作中提到】
: 当然是O(N)的
: http://www.mitbbs.com/article_t/JobHunting/31875095.html
: 这里有 darksteel 详解
| a*******6
发帖数: 520 | 14 int maxA[N + 1];
int bestS = -1, bestT = -1, s, t, i;
maxA[N] = -INFNITY;
maxA[N - 1] = a[N - 1];
for (i = N - 2; i >= 0; i--)
maxA[i] = max(maxA[i], maxA[i + 1]);
for (i = 0; i < N - 1; i++)
if (a[i] < maxA[i + 1])
break;
if (i == N - 1)
return false;
else
s = i;
t = 0;
while (t < N)
{
t = max(t, s);
while (a[s] < maxA[t + 1])
t++;
if (t - s > bestT - bestS)
{
bestS = s;
bestT = t;
}
for (i = s + 1; i < N - 1; i++)
if (a[i] < a[s])
break;
if (i < N - 1)
s = i;
else
break;
}
*resi = bestS;
*resj = bestT;
return true;
【在 k***t 的大作中提到】
: 网上看到的真题。自己写了一个答案，还算简洁，但对时间复杂度和不满意。
: 抛砖引玉吧。哪位来个O(n)的解？
: boolean maxji (int a[], int N, int *resi, int *resj) {
: int i, j, previ, maxdist, maxi;
: if (!a || (N < 2) || !resi || !resj) return FALSE;
: j = N-1;
: while((a[j] <= a[0]) && (j != 0)) --j;
: previ = 0; maxi = 0; maxdist = j - 0;
: for (i = 1; i < (N-maxdist-1); ++i) {
: if (a[i] >= a[previ]) continue;
| m********l
发帖数: 4394 | 15 .. not sure, is this right?
【在 k***t 的大作中提到】
: 网上看到的真题。自己写了一个答案，还算简洁，但对时间复杂度和不满意。
: 抛砖引玉吧。哪位来个O(n)的解？
: boolean maxji (int a[], int N, int *resi, int *resj) {
: int i, j, previ, maxdist, maxi;
: if (!a || (N < 2) || !resi || !resj) return FALSE;
: j = N-1;
: while((a[j] <= a[0]) && (j != 0)) --j;
: previ = 0; maxi = 0; maxdist = j - 0;
: for (i = 1; i < (N-maxdist-1); ++i) {
: if (a[i] >= a[previ]) continue;
| k***t
发帖数: 276 | 16 The main part should be functional correct. It passed my test cases. There
might be boundary cases to cover though, not sure.
Got an improved version with comparison skipping on the right side. Not an O
(n), but should be close in a normal case as lots of comparisons are indeed
skipped. For this kind of questions, if it was never seen, I would be more
than happy if I could ever reach this far in an interview:)
#include
using namespace std;
bool maxji (int a[], int N, int *resi, int *resj) {
int i, j, k;
int previ, prevj, maxdist, maxi;
vector prevjarr;
if (!a || (N < 2) || !resi || !resj) return false;
j = N-1; prevj = -32767;
while((a[j] <= a[0]) && (j != 0)) {
if (a[j] > prevj) {
prevjarr.push_back(j);
prevj = a[j];
}
--j;
}
previ = 0; maxi = 0; maxdist = j - 0;
for (i = 1; i < (N-maxdist-1); ++i) {
if (a[i] >= a[previ]) continue;
previ = i; j = prevjarr.front(); k = 0;
prevj = a[prevjarr.back()];
while((a[j] <= a[i]) && (j != i)) {
if (j > prevjarr.back()) {
j = prevjarr[++k];
} else {
if (a[j] > prevj) {
prevj = a[j];
prevjarr.push_back(j);
}
--j;
}
}
if ((j - i) > maxdist) {
maxi = i; maxdist = j - i;
}
}
*resi = maxi; *resj = maxi + maxdist;
return true;
}
【在 m********l 的大作中提到】
: .. not sure, is this right?
| b*****e
发帖数: 131 | | s******n
发帖数: 226 | 18 int MaxInt(int a[], int n){
vector s;
vector::iterator iter;
for(int i=0;i
if(!s.empty() && a[i]>=a[s.back()]) continue;
s.push_back(i);
}
int max =0;
for(int i=n-1;i>=0;i--){
while(!s.empty() && a[i]>a[s.back()]) s.pop_back();
if(s.empty()) return i;
if(max
}
return max;
【在 a*****n 的大作中提到】
: 不能用stack吧，所有的最小值得存起来，留给下次比较。
| s******n
发帖数: 226 | | g***x
发帖数: 494 | 20 不是有个典型的解法吗？
int maxdist(int *a, int num)
{
int *min=new int[num];
int *max=new int[num];
int i,j,k;
int t=INT_MAX;
for(i=0;i
{
if(a[i]
min[i]=a[i];
t=a[i];
}
else
min[i]=t;
}
t=INT_MIN;
for(i=num-1,i>=0;i--){
if(a[i]>t){
max[i]=a[i];
t=a[i];
}
else
max[i]=t;
}
i=0;j=0;
dist=-1;
while(i
if(min[i]
dist=max(dist, j-1);
j++;}
else
i++;
}
return dist;
}
空间复杂度n，min可以用一个变量代替，max不知道可不可以用什么方法去掉？
}
}
【在 b*****e 的大作中提到】
: 不太可能有O(n)解，再看看...
| | | m********l
发帖数: 4394 | 21 看了下别人的答案， 顺便问下这题目的意思是
1) Find (i,j) in array A to max (j - i) for ANY j, i as long as Aj>Ai
2) Find (i,j) in array A to max (j - i) for ALL j, i such that Aj>Ai
e.g.
a = 1 3 2 4
what's the expected result
【在 k***t 的大作中提到】
: 网上看到的真题。自己写了一个答案，还算简洁，但对时间复杂度和不满意。
: 抛砖引玉吧。哪位来个O(n)的解？
: boolean maxji (int a[], int N, int *resi, int *resj) {
: int i, j, previ, maxdist, maxi;
: if (!a || (N < 2) || !resi || !resj) return FALSE;
: j = N-1;
: while((a[j] <= a[0]) && (j != 0)) --j;
: previ = 0; maxi = 0; maxdist = j - 0;
: for (i = 1; i < (N-maxdist-1); ++i) {
: if (a[i] >= a[previ]) continue;
| n*******w
发帖数: 687 | 22 容易证明是O(n)。
darksteel这个想法太巧妙了。
【在 b*******y 的大作中提到】
: ic
: 好像是有两个loop，但数学证明还是O(n)的，是吧？
| k***t
发帖数: 276 | 23 看了一下darksteel的答案，从右向左检查左下标待选序列，右下标就可以单调
从而保证O(n)了。确实不错！
不过，在不否认darksteel好的前提下，个人以为，实际中，从左检查或许会更早找到
答案：）
1。如果加上合适pruning，如局部maxdist大于(N-i)时即找到答案，此时甚至还未遍
历整个数组即收敛；
2。对任何下一个左下标待选，右下标的查找范围递减，不会超过前一个的。从这个意
义上讲，这种算法可能也是O(n)。N/2+N/4+... <= N，不是吗？
O
indeed
【在 k***t 的大作中提到】
: The main part should be functional correct. It passed my test cases. There
: might be boundary cases to cover though, not sure.
: Got an improved version with comparison skipping on the right side. Not an O
: (n), but should be close in a normal case as lots of comparisons are indeed
: skipped. For this kind of questions, if it was never seen, I would be more
: than happy if I could ever reach this far in an interview:)
: #include
: using namespace std;
: bool maxji (int a[], int N, int *resi, int *resj) {
: int i, j, k;
| k***t
发帖数: 276 | 24 Given an array A[], find (i, j) such that A[i] < A[j] and (j - i) is maximum.
a = 1 3 2 4 的答案是无解:)
【在 m********l 的大作中提到】
: 看了下别人的答案， 顺便问下这题目的意思是
: 1) Find (i,j) in array A to max (j - i) for ANY j, i as long as Aj>Ai
: 2) Find (i,j) in array A to max (j - i) for ALL j, i such that Aj>Ai
: e.g.
: a = 1 3 2 4
: what's the expected result
| e****r
发帖数: 28 | 25 Basically Agree with nooneknow - it's not clear that what would be the expected or average big-O of darksteel solution. at least, in the case of a non-increasing sorted array, it takes much more time than O(n).
Also agree with Kirit(jack) - in the situation of interview, it's better to try the straightforward solution, get the code done, and try to reduce bugs. the coder can mention the potential sorting + O(N) post-process solution to the interviewer, though :).
btw, how many minutes do you guys think the coder could have in the coding task (like this question)?
best,
(this post is revised by the author after a second read about 1337 coder's article. sorry for being potentially misleading :) )
【在 n*******w 的大作中提到】
: 1337那题没时间写完吧。
: 最后那个O(n)的算法并不是O(n)。反例比如，worst case是逆序数组，要O(n^2)。
: 这题看过几个网站给的O(n)解法，包括用stack记录最大最小，分段等等，都不是O(n)
: 解甚至有些是错的。
| c*******t
发帖数: 39 | 26 Some thought:
Do two scans:
1. from left to right, for each element mark the minimal element seen so far
2. from right to left, for each element mark the maximal element seen so far
Then do a third scan from left to right:
Start from the first element, go as far as possible until the marked maximal
element is smaller than it and record the current j-i
Then find next possible left start point, which is the element has minimal
mark equal to itself and less than the current maximal of element at j.
repeat and change j-i if necessary.
I think it is O(n) since it just contains scans and avoid unnecessary
comparison by each time starting at least old j | n*******w
发帖数: 687 | 27 能写个伪码么？
我记得这个解法有严重的bug。
far
far
maximal
【在 c*******t 的大作中提到】
: Some thought:
: Do two scans:
: 1. from left to right, for each element mark the minimal element seen so far
: 2. from right to left, for each element mark the maximal element seen so far
: Then do a third scan from left to right:
: Start from the first element, go as far as possible until the marked maximal
: element is smaller than it and record the current j-i
: Then find next possible left start point, which is the element has minimal
: mark equal to itself and less than the current maximal of element at j.
: repeat and change j-i if necessary.
|
|
|
|
|
|
|
|
