b***u
发帖数: 61 | 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*****t
发帖数: 335 | 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*****a
发帖数: 14598 | 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*****t
发帖数: 335 | 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(j
res.resize(j-i-1);
copy(arr.begin()
【在 l*****a 的大作中提到】
: could u write code for this if there are duplicate here
|
l*****a
发帖数: 14598 | 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*******n
发帖数: 112 | 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*****t
发帖数: 335 | 7 if there are duplicates, binary search is not working
【在 l*****a 的大作中提到】
: what is your result for {0,2,2}?
|
r*****e
发帖数: 7853 | 8 sorted, use bisection, 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*****a
发帖数: 14598 | 9 sorry that i still think below two steps are O(n)
while(i>=0&&arr[i]==i) i--;
while(j
【在 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 {
|
l*****a
发帖数: 14598 | 10 please share us your code,or details steps
thanks
【在 r*****e 的大作中提到】
: sorted, use bisection, O(logn)
:
: to
|
|
|
l*****a
发帖数: 14598 | 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*****e
发帖数: 7853 | 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***u
发帖数: 61 | 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****n
发帖数: 233 | 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***u
发帖数: 61 | 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];
|
