由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 谁能解释下careerUp上18.3这题吗?
相关主题
WalmartLab面经最长递增子array的算法
Search in a sorted, rotated list问一道老题
search in a rotated array继续攒人品 报几家面经
问一个search in rotated array的问题问大家关于编程的经验
lc新题,贴个刚写的solutionamazon 电面题
binary search in rotated sorted array有重复时怎么办?问一道题
有没有人总结过binary search是mid加减1和小于或者等于的情况分类这题也可以DP 解吧?
binary search什么时候用lleetcode的valid number的考点在哪里呢?
相关话题的讨论汇总
话题: int话题: else话题: search话题: sorted话题: location
进入JobHunting版参与讨论
1 (共1页)
r******n
发帖数: 170
1
Given a sorted array of n integers that has been rotated an unknown number
of times, give an O(log n) algorithm that finds an element in the array. You
may assume that the array was originally sorted in increasing order。
int search(int a[], int l, int u, int x) {
while (l <= u) {
int m = (l + u) / 2;
if (x == a[m]) {
return m;
} else if (a[l] <= a[m]) {
if (x > a[m]) {
l=m+1;
} else if (x >=a [l]) {
u = m-1;
} else {
l = m+1;
}
}
else if (x < a[m]) u = m-1;
else if (x <= a[u]) l = m+1;
else u = m-1;
}
return -1;
}
没看懂解答为啥能保证是对的?
c**********s
发帖数: 410
2

You

【在 r******n 的大作中提到】
: Given a sorted array of n integers that has been rotated an unknown number
: of times, give an O(log n) algorithm that finds an element in the array. You
: may assume that the array was originally sorted in increasing order。
: int search(int a[], int l, int u, int x) {
: while (l <= u) {
: int m = (l + u) / 2;
: if (x == a[m]) {
: return m;
: } else if (a[l] <= a[m]) {
: if (x > a[m]) {

x******g
发帖数: 41
3
二分的变体呀
通过比较a[l]和a[m]判断数组的哪一半是单调的或者rotated
v*s
发帖数: 946
4
假设旋转前的数组是1到11.
旋转后有两种可能性。
case 1)
8,9,10,11, 1,2,3,4,5,6,7
case 2)
4,5,6,7,8,9,10,11, 1,2,3
还是中间切一刀。先比中间那个数,如果lucky,那就找到了。
否则决定要选哪边继续比较。
如果 a[l] < a[m] 说明前半截是顺序的,例如上面的case 2)
>>>> 如果 a[l] <= x < a[m] 那就选前半截,否则选后半截。
否则 ( 说明后半截是顺序的,参考case 1))
>>>> 如果 a[m] < x <= a[u] 那就选前后截,否则选前半截。
以此类推。
主要考点: 二分法,一刀分成两截,只和顺序的那半截进行比较。如果确定不在那里
面,就在乱序的那半截。

You

【在 r******n 的大作中提到】
: Given a sorted array of n integers that has been rotated an unknown number
: of times, give an O(log n) algorithm that finds an element in the array. You
: may assume that the array was originally sorted in increasing order。
: int search(int a[], int l, int u, int x) {
: while (l <= u) {
: int m = (l + u) / 2;
: if (x == a[m]) {
: return m;
: } else if (a[l] <= a[m]) {
: if (x > a[m]) {

s*****n
发帖数: 5488
5
拿几个测试例子走走,根本这就不对。
6712345

You

【在 r******n 的大作中提到】
: Given a sorted array of n integers that has been rotated an unknown number
: of times, give an O(log n) algorithm that finds an element in the array. You
: may assume that the array was originally sorted in increasing order。
: int search(int a[], int l, int u, int x) {
: while (l <= u) {
: int m = (l + u) / 2;
: if (x == a[m]) {
: return m;
: } else if (a[l] <= a[m]) {
: if (x > a[m]) {

v*s
发帖数: 946
6
较真的我喜欢。 我还真的放在gcc里跑了一圈。是对的啊。
int aa[] = { 6,7,1,2,3,4,5};
int main(void)
{
int i;
for(i=0;i<=10;++i)
{
printf("search for %d, location: %d\n", i ,search(aa, 0, 6, i));
}
}
$ ./a.out
search for 0, location: -1
search for 1, location: 2
search for 2, location: 3
search for 3, location: 4
search for 4, location: 5
search for 5, location: 6
search for 6, location: 0
search for 7, location: 1
search for 8, location: -1
search for 9, location: -1
search for 10, location: -1

【在 s*****n 的大作中提到】
: 拿几个测试例子走走,根本这就不对。
: 6712345
:
: You

r******n
发帖数: 170
7
多谢详细的解释,我没注意到一个简单的事实,随便砍一刀,肯定只有一边是乱序,一
边是递增
的。
然后就是判断到底是在递增的区域,还是在乱序的区域了。假如在递增的区域,马上就
变成binary
search;不在递增区域,就划分到乱序区域继续砍。
下标应该也可以改成:
int search(int a[], int l, int u, int x) {
while (l <= u)
{
int m = (l + u) / 2;
if (x == a[m])
{
return m;
}
else if (a[l] <= a[m])
{
if (x < a[l])
{
l=m+1;
}
else if (x {
u = m-1;
}
else
{
l = m+1;
}
}
else if (x > a[u])
u = m-1;
else if (x >a[m])
l = m+1;
else
u = m-1;
}

i));

【在 v*s 的大作中提到】
: 较真的我喜欢。 我还真的放在gcc里跑了一圈。是对的啊。
: int aa[] = { 6,7,1,2,3,4,5};
: int main(void)
: {
: int i;
: for(i=0;i<=10;++i)
: {
: printf("search for %d, location: %d\n", i ,search(aa, 0, 6, i));
: }
: }

r******n
发帖数: 170
8
Given a sorted array of n integers that has been rotated an unknown number
of times, give an O(log n) algorithm that finds an element in the array. You
may assume that the array was originally sorted in increasing order。
int search(int a[], int l, int u, int x) {
while (l <= u) {
int m = (l + u) / 2;
if (x == a[m]) {
return m;
} else if (a[l] <= a[m]) {
if (x > a[m]) {
l=m+1;
} else if (x >=a [l]) {
u = m-1;
} else {
l = m+1;
}
}
else if (x < a[m]) u = m-1;
else if (x <= a[u]) l = m+1;
else u = m-1;
}
return -1;
}
没看懂解答为啥能保证是对的?
c**********s
发帖数: 410
9

You

【在 r******n 的大作中提到】
: Given a sorted array of n integers that has been rotated an unknown number
: of times, give an O(log n) algorithm that finds an element in the array. You
: may assume that the array was originally sorted in increasing order。
: int search(int a[], int l, int u, int x) {
: while (l <= u) {
: int m = (l + u) / 2;
: if (x == a[m]) {
: return m;
: } else if (a[l] <= a[m]) {
: if (x > a[m]) {

x******g
发帖数: 41
10
二分的变体呀
通过比较a[l]和a[m]判断数组的哪一半是单调的或者rotated
相关主题
binary search in rotated sorted array有重复时怎么办?最长递增子array的算法
有没有人总结过binary search是mid加减1和小于或者等于的情况分类问一道老题
binary search什么时候用l继续攒人品 报几家面经
进入JobHunting版参与讨论
s*****n
发帖数: 5488
11
拿几个测试例子走走,根本这就不对。
6712345

You

【在 r******n 的大作中提到】
: Given a sorted array of n integers that has been rotated an unknown number
: of times, give an O(log n) algorithm that finds an element in the array. You
: may assume that the array was originally sorted in increasing order。
: int search(int a[], int l, int u, int x) {
: while (l <= u) {
: int m = (l + u) / 2;
: if (x == a[m]) {
: return m;
: } else if (a[l] <= a[m]) {
: if (x > a[m]) {

r******n
发帖数: 170
12
多谢详细的解释,我没注意到一个简单的事实,随便砍一刀,肯定只有一边是乱序,一
边是递增
的。
然后就是判断到底是在递增的区域,还是在乱序的区域了。假如在递增的区域,马上就
变成binary
search;不在递增区域,就划分到乱序区域继续砍。
下标应该也可以改成:
int search(int a[], int l, int u, int x) {
while (l <= u)
{
int m = (l + u) / 2;
if (x == a[m])
{
return m;
}
else if (a[l] <= a[m])
{
if (x < a[l])
{
l=m+1;
}
else if (x {
u = m-1;
}
else
{
l = m+1;
}
}
else if (x > a[u])
u = m-1;
else if (x >a[m])
l = m+1;
else
u = m-1;
}

i));

【在 v*s 的大作中提到】
: 较真的我喜欢。 我还真的放在gcc里跑了一圈。是对的啊。
: int aa[] = { 6,7,1,2,3,4,5};
: int main(void)
: {
: int i;
: for(i=0;i<=10;++i)
: {
: printf("search for %d, location: %d\n", i ,search(aa, 0, 6, i));
: }
: }

d*******u
发帖数: 186
13
比较element和中间元素, 如果相同返回。
否则递归找该element在左边和右边:
左边: rotated sorted or sorted.
ratated sorted: recursive.
sorted: binary search.
similarly for the right side.

You

【在 r******n 的大作中提到】
: Given a sorted array of n integers that has been rotated an unknown number
: of times, give an O(log n) algorithm that finds an element in the array. You
: may assume that the array was originally sorted in increasing order。
: int search(int a[], int l, int u, int x) {
: while (l <= u) {
: int m = (l + u) / 2;
: if (x == a[m]) {
: return m;
: } else if (a[l] <= a[m]) {
: if (x > a[m]) {

d*******u
发帖数: 186
14
比较element和中间元素, 如果相同返回。
否则递归找该element在左边和右边:
左边: rotated sorted or sorted.
ratated sorted: recursive.
sorted: binary search.
similarly for the right side.

You

【在 r******n 的大作中提到】
: Given a sorted array of n integers that has been rotated an unknown number
: of times, give an O(log n) algorithm that finds an element in the array. You
: may assume that the array was originally sorted in increasing order。
: int search(int a[], int l, int u, int x) {
: while (l <= u) {
: int m = (l + u) / 2;
: if (x == a[m]) {
: return m;
: } else if (a[l] <= a[m]) {
: if (x > a[m]) {

z******t
发帖数: 59
15
这个博客里有这个问题详细的解答:
http://zhedahht.blog.163.com/blog/static/2541117420095276512054

You

【在 r******n 的大作中提到】
: Given a sorted array of n integers that has been rotated an unknown number
: of times, give an O(log n) algorithm that finds an element in the array. You
: may assume that the array was originally sorted in increasing order。
: int search(int a[], int l, int u, int x) {
: while (l <= u) {
: int m = (l + u) / 2;
: if (x == a[m]) {
: return m;
: } else if (a[l] <= a[m]) {
: if (x > a[m]) {

q****x
发帖数: 7404
16
why you need x?

You

【在 r******n 的大作中提到】
: Given a sorted array of n integers that has been rotated an unknown number
: of times, give an O(log n) algorithm that finds an element in the array. You
: may assume that the array was originally sorted in increasing order。
: int search(int a[], int l, int u, int x) {
: while (l <= u) {
: int m = (l + u) / 2;
: if (x == a[m]) {
: return m;
: } else if (a[l] <= a[m]) {
: if (x > a[m]) {

1 (共1页)
进入JobHunting版参与讨论
相关主题
leetcode的valid number的考点在哪里呢?lc新题,贴个刚写的solution
请教一个常见的面试题的答案binary search in rotated sorted array有重复时怎么办?
median of an array of ints, 请问这题的经典回答是什么?谢谢有没有人总结过binary search是mid加减1和小于或者等于的情况分类
求一下这题解法。binary search什么时候用l
WalmartLab面经最长递增子array的算法
Search in a sorted, rotated list问一道老题
search in a rotated array继续攒人品 报几家面经
问一个search in rotated array的问题问大家关于编程的经验
相关话题的讨论汇总
话题: int话题: else话题: search话题: sorted话题: location