看板Oversea_Job
标 题Re: Microsoft Interview Question
发信站批踢踢参 (Sun Jan 27 15:11:29 2008)
转信站ptt!Group.NCTU!grouppost!Group.NCTU!ptt3
※ 引述《[email protected] (Sunnyvale)》之铭言：
: ※ 引述《Baudelaire (Sunnyvale)》之铭言：
: 基本上算是binary search的变形：
: public static int FindSortedArrayRotation(int array[]) {
: int begin = 0, end = array.length - 1;
: while (end-begin>1) {
: if (array[begin] > array[(begin + end) / 2]) {
: end = (begin + end) / 2;
: } else if (array[(begin + end) / 2] > array[end]) {
: begin = (begin + end) / 2;
: } else {
: return (begin+end)/2+1;
: }
: }
: return end;
: }
我想方向是正确的, 但是如果 X = 0 的话,似乎会有问题.....
我精简你的版本,在最後return前确定是真的rotate过.
public static int FindSortedArrayRotation(int array[]) {
int i = 0, j = array.length -1;
while(j-i > 1)
{
if(array[(i+j)/2] > array[i])
i = (i+j)/2;
else
j = (i+j)/2;
}
if(array[j] < array[i])
return j; // Make sure array did rotate.
else
return 0 ;
欢迎指正
--
※ 发信站: 批踢踢参(ptt3.cc)
◆ From: 168.7.230.23