K******g
发帖数: 1870 | 1 find out all the elements in a sorted integer array whose value is equal to
index of the array. O(logn) solution is expected.
请不要随便说个binary search，那样等于没有说。请教一个很详细的步骤，并且有例
子。多谢！ |
o***i
发帖数: 603 | 2 既然已经sorted了，难道不是O(n)就可以了？扫描一遍就ok了呀
to
【在 K******g 的大作中提到】
: find out all the elements in a sorted integer array whose value is equal to
: index of the array. O(logn) solution is expected.
: 请不要随便说个binary search，那样等于没有说。请教一个很详细的步骤，并且有例
: 子。多谢！
|
c*********e
发帖数: 62 | 3 how could O(logn) be possible if the array looks like below:
[0, 1, 2, 3, 4, 5, 6, 7, ..., ]
that is, each element's value = its own index
in the worst case, you have to scan all the elements. O(n)
to
【在 K******g 的大作中提到】
: find out all the elements in a sorted integer array whose value is equal to
: index of the array. O(logn) solution is expected.
: 请不要随便说个binary search，那样等于没有说。请教一个很详细的步骤，并且有例
: 子。多谢！
|
i*****e
发帖数: 5233 | 4 agree
how could O(logn) be possible if the array looks like below:
[0, 1, 2, 3, 4, 5, 6, 7, ..., ]
that is, each element's value = its own index
in the worst case, you have to scan all the elements. O(n)
to
【在 c*********e 的大作中提到】
: how could O(logn) be possible if the array looks like below:
: [0, 1, 2, 3, 4, 5, 6, 7, ..., ]
: that is, each element's value = its own index
: in the worst case, you have to scan all the elements. O(n)
:
: to
|
g****n
发帖数: 431 | 5 在所有元素都unique的情况下，可以用log(n)时间找出所有value = index的元素的
range，因为
这样的range只能有一个，这样这个题就变成了用log(n)时间找出最小的和最大的value
= index的
元素（range边界）了。
假设排序是递增的，用2步分别找最小和最大元素。
1. 找最小：用b-search的方法，找到mid-index后，比较value是否大于index。如果大
于，则目标
在左half。如果小于，则目标在右。如果等于，目标还是在左。
2. 找最大：把等于的情况，改成目标在右。
【在 c*********e 的大作中提到】
: how could O(logn) be possible if the array looks like below:
: [0, 1, 2, 3, 4, 5, 6, 7, ..., ]
: that is, each element's value = its own index
: in the worst case, you have to scan all the elements. O(n)
:
: to
|
f*********5
发帖数: 576 | 6 why?
for example.sizeof(a)=8
lo=0,hi=8 //lo mean start index of binary search
// hi means end index of binary search
mid=(lo+hi)/2;
when u found that a[mid]=mid
u don't need to check a[0]..a[mid-1]...
then u can use binary search...
make sense?
【在 c*********e 的大作中提到】
: how could O(logn) be possible if the array looks like below:
: [0, 1, 2, 3, 4, 5, 6, 7, ..., ]
: that is, each element's value = its own index
: in the worst case, you have to scan all the elements. O(n)
:
: to
|
g****n
发帖数: 431 | 7 所有value=index的数在一个并且只在一个range中，是个隐含的性质。找到了这个性质
，就可以很容
易想到找range的边界了，复杂度仍然是log(n)。当然，如果要打印出这些数，那么复
杂度就是(n)了。
equal to
【在 K******g 的大作中提到】
: find out all the elements in a sorted integer array whose value is equal to
: index of the array. O(logn) solution is expected.
: 请不要随便说个binary search，那样等于没有说。请教一个很详细的步骤，并且有例
: 子。多谢！
|
g****n
发帖数: 431 | 8 很不make sense。按你说的，如果lo=0,hi=8并且n=8，因为数列是有序的，那根本不用
任何check整
个数列就是解。
如果不是这种情况，你的方法我不知道是什么意思。
【在 f*********5 的大作中提到】
: why?
: for example.sizeof(a)=8
: lo=0,hi=8 //lo mean start index of binary search
: // hi means end index of binary search
: mid=(lo+hi)/2;
: when u found that a[mid]=mid
: u don't need to check a[0]..a[mid-1]...
: then u can use binary search...
: make sense?
|
i*****e
发帖数: 5233 | 9 Thanks 理解你的意思了 也就是说 原题实际就是在用b-search找两个边界
【在 g****n 的大作中提到】
: 所有value=index的数在一个并且只在一个range中，是个隐含的性质。找到了这个性质
: ，就可以很容
: 易想到找range的边界了，复杂度仍然是log(n)。当然，如果要打印出这些数，那么复
: 杂度就是(n)了。
:
: equal to
|
g****n
发帖数: 431 | 10 我认为是这样的，这是这题的一个隐含性质。
【在 i*****e 的大作中提到】
: Thanks 理解你的意思了 也就是说 原题实际就是在用b-search找两个边界
|
|
|
Z*****Z
发帖数: 723 | 11 这个方法可以扩展到在sorted数组里面找一个给定元素吧，数组允许重复。也是找2次，
一次下界一次上界
value
【在 g****n 的大作中提到】
: 在所有元素都unique的情况下，可以用log(n)时间找出所有value = index的元素的
: range，因为
: 这样的range只能有一个，这样这个题就变成了用log(n)时间找出最小的和最大的value
: = index的
: 元素（range边界）了。
: 假设排序是递增的，用2步分别找最小和最大元素。
: 1. 找最小：用b-search的方法，找到mid-index后，比较value是否大于index。如果大
: 于，则目标
: 在左half。如果小于，则目标在右。如果等于，目标还是在左。
: 2. 找最大：把等于的情况，改成目标在右。
|
f*********5
发帖数: 576 | 12 如果a[mid]!=mid,then u only need to check a[0]..a[mid-1]
u can ignore a[mid+1]..a[n]
since it is impossible that a[mid]
简单说，这道题就是binary search找一个位置。
你找到第一个不是a[index]==index的以后，后面的都不拢考虑了
前面的就是结果
【在 g****n 的大作中提到】
: 很不make sense。按你说的，如果lo=0,hi=8并且n=8，因为数列是有序的，那根本不用
: 任何check整
: 个数列就是解。
: 如果不是这种情况，你的方法我不知道是什么意思。
|
g****n
发帖数: 431 | 13 "since it is impossible that a[mid]
负数。这就是为什么我说那个range有两个边界。
【在 f*********5 的大作中提到】
: 如果a[mid]!=mid,then u only need to check a[0]..a[mid-1]
: u can ignore a[mid+1]..a[n]
: since it is impossible that a[mid]: 简单说，这道题就是binary search找一个位置。
: 你找到第一个不是a[index]==index的以后，后面的都不拢考虑了
: 前面的就是结果
|
f*********5
发帖数: 576 | 14 en
这点我忽视了。
看题不仔细啊。。
【在 g****n 的大作中提到】
: "since it is impossible that a[mid]: 负数。这就是为什么我说那个range有两个边界。
|
g****n
发帖数: 431 | 15 恩，有道理
次，
【在 Z*****Z 的大作中提到】
: 这个方法可以扩展到在sorted数组里面找一个给定元素吧，数组允许重复。也是找2次，
: 一次下界一次上界
:
: value
|
j**l
发帖数: 2911 | 16 我开始把原题看成你说的这题了。
如果是你这题
第一步，如果有相同元素，找到index最小的那个
第二步，如果有相同元素，找到index最大的那个
Programming Pearls上有讨论怎么做这种变体的方法，思路就是当mid元素等于待查元
素时候让
lower = mid 或 upper = mid, 并且在还剩两个元素的时候就要停止
次，
【在 Z*****Z 的大作中提到】
: 这个方法可以扩展到在sorted数组里面找一个给定元素吧，数组允许重复。也是找2次，
: 一次下界一次上界
:
: value
|
K******g
发帖数: 1870 | 17 不错。好像很对。
value
【在 g****n 的大作中提到】
: 在所有元素都unique的情况下，可以用log(n)时间找出所有value = index的元素的
: range，因为
: 这样的range只能有一个，这样这个题就变成了用log(n)时间找出最小的和最大的value
: = index的
: 元素（range边界）了。
: 假设排序是递增的，用2步分别找最小和最大元素。
: 1. 找最小：用b-search的方法，找到mid-index后，比较value是否大于index。如果大
: 于，则目标
: 在左half。如果小于，则目标在右。如果等于，目标还是在左。
: 2. 找最大：把等于的情况，改成目标在右。
|
s********l
发帖数: 998 | |
f*********5
发帖数: 576 | 19 不对
如果是 a[index]==index && a[index +/- 1]=index
就不满足题意了，
【在 s********l 的大作中提到】
: 这题如果有重复元素的话 只能o(n)吧？
|
s********l
发帖数: 998 | 20 题目没说 array都是unique value啊~
可以这样子吧~
1 1 1 2 5 6 7...
【在 f*********5 的大作中提到】
: 不对
: 如果是 a[index]==index && a[index +/- 1]=index
: 就不满足题意了，
|
h**6
发帖数: 4160 | 21 如果所有元素都不同，可以把所有元素减去其下标，可以证明新数组仍然是有序的
，这时用二分法找出值为0的元素的起止位置。
第一步减下标复杂度为O(n)，但是可以不实际减，仅仅在脑海中想象减，这样直接进
行第二步，复杂度为O(log n)。
如果没有所有元素不同的条件，还是老老实实一个一个比较吧，复杂度O(n)。 |
