avatar
B*t
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 ?

avatar
l*a
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

avatar
B*t
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
avatar
l*a
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 {

avatar
c*n
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).
avatar
B*t
7
if there are duplicates, binary search is not working

【在 l*****a 的大作中提到】
: what is your result for {0,2,2}?
avatar
r*e
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 ?

avatar
l*a
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 {

avatar
l*a
10
please share us your code,or details steps
thanks

【在 r*****e 的大作中提到】
: sorted, use bisection, O(logn)
:
: to

avatar
l*a
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).

avatar
r*e
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,

avatar
b*u
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))?

avatar
d*n
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对于该算法而言并无变化

avatar
b*u
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];

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。