请教一道题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

请教一道题

请教一道题# JobHunting - 待字闺中

b*u2010-05-14 07:05

1 楼

http://www.careercup.com/question?id=2152665
find out all the elements in a sorted integer array whose value is equal to
index of the array.
这个题可能有O(logn)的解吗咋觉得不可能呢
比如A={-1 0 2 2 3 4} 不遍历整个A怎么可能知道A[2]=2 ?

B*t2010-05-14 07:05

2 楼

in the worst case, it is O(n), for example, a[i]=i; 1<=i<=n;
but average case is O(logn)

to

【在 b***u 的大作中提到】

: http://www.careercup.com/question?id=2152665
: find out all the elements in a sorted integer array whose value is equal to
: index of the array.
: 这个题可能有O(logn)的解吗咋觉得不可能呢
: 比如A={-1 0 2 2 3 4} 不遍历整个A怎么可能知道A[2]=2 ?

l*a2010-05-14 07:05

3 楼

could u write code for this if there are duplicate here

【在 B*****t 的大作中提到】

: in the worst case, it is O(n), for example, a[i]=i; 1<=i<=n;
: but average case is O(logn)
:
: to

B*t2010-05-14 07:05

4 楼

here is the code, plz let me know if there is any bug.
vector findElement(const vector &arr) {
int i, j, mid;
vector res;
i = 0, j = arr.size() - 1;
while(i<=j) {
mid = i+(j-i)/2;
if(arr[mid]>mid) j = mid - 1;
else if(arr[mid]else {
i = mid - 1, j = mid + 1;
while(i>=0&&arr[i]==i) i--;
while(jres.resize(j-i-1);
copy(arr.begin()

【在 l*****a 的大作中提到】

: could u write code for this if there are duplicate here

l*a2010-05-14 07:05

5 楼

what is your result for {0,2,2}?

【在 B*****t 的大作中提到】

: here is the code, plz let me know if there is any bug.
: vector findElement(const vector &arr) {
: int i, j, mid;
: vector res;
: i = 0, j = arr.size() - 1;
: while(i<=j) {
: mid = i+(j-i)/2;
: if(arr[mid]>mid) j = mid - 1;
: else if(arr[mid]: else {

c*n2010-05-14 07:05

6 楼

I think O(logn) solution is possible. Since the array is sorted, you can
solve the problem by finding the smallest and largest index such a[i] = i,
which should be able to solved with O(logn).

B*t2010-05-14 07:05

7 楼

if there are duplicates, binary search is not working

【在 l*****a 的大作中提到】

: what is your result for {0,2,2}?

r*e2010-05-14 07:05

8 楼

sorted, use bisection, O(logn)

to

【在 b***u 的大作中提到】

l*a2010-05-14 07:05

9 楼

sorry that i still think below two steps are O(n)
while(i>=0&&arr[i]==i) i--;
while(j
【在 B*****t 的大作中提到】

l*a2010-05-14 07:05

10 楼

please share us your code,or details steps
thanks

【在 r*****e 的大作中提到】

: sorted, use bisection, O(logn)
:
: to

l*a2010-05-14 07:05

11 楼

please share us your code,or details steps
thanks

i,

【在 c*******n 的大作中提到】

: I think O(logn) solution is possible. Since the array is sorted, you can
: solve the problem by finding the smallest and largest index such a[i] = i,
: which should be able to solved with O(logn).

r*e2010-05-14 07:05

12 楼

After a second thought, I believe O(n) is needed for a general case,
e.g., 0,0,2,2,...,n,n; there are n/2 such numbers. How can we identify all
of them with (O(logn))?

【在 l*****a 的大作中提到】

: please share us your code,or details steps
: thanks
:
: i,

b*u2010-05-14 07:05

13 楼

这是一种情况
另一种情况是对于数组 A[i]=i-1
只有遍历整个A才能确定不存在A[i]=i
否则总可以将该算法没有访问到的元素比如A[i0]的值改成A[i0]=i0
此时整个A仍然是升序的而该算法的输出结果仍然是不存在A[i]=i
因为A对于该算法而言并无变化

【在 r*****e 的大作中提到】

: After a second thought, I believe O(n) is needed for a general case,
: e.g., 0,0,2,2,...,n,n; there are n/2 such numbers. How can we identify all
: of them with (O(logn))?

d*n2010-05-14 07:05

14 楼

Someone had the following idea
ArrayList Find(ArrayList AL)
{
ArrayList result = new ArrayList ();
int index =0;
while (index < AL.size())
{
if (AL[index] > index)
{
index = AL[index];
}
else
{
if (AL[index] == index)
result.Add(index);
++index;
}
}

return result;
}

【在 b***u 的大作中提到】

: 这是一种情况
: 另一种情况是对于数组 A[i]=i-1
: 只有遍历整个A才能确定不存在A[i]=i
: 否则总可以将该算法没有访问到的元素比如A[i0]的值改成A[i0]=i0
: 此时整个A仍然是升序的而该算法的输出结果仍然是不存在A[i]=i
: 因为A对于该算法而言并无变化

b*u2010-05-14 07:05

15 楼

if (AL[index] == index)
result.Add(index);
++index;
这部分在一个一个试？

【在 d****n 的大作中提到】

: Someone had the following idea
: ArrayList Find(ArrayList AL)
: {
: ArrayList result = new ArrayList ();
: int index =0;
: while (index < AL.size())
: {
: if (AL[index] > index)
: {
: index = AL[index];