Re: Microsoft Interview Question
※ 引述《Baudelaire.bbs@ptt.cc (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
討論串 (同標題文章)
Oversea_Job 近期熱門文章
PTT職涯區 即時熱門文章
