Re: Microsoft Interview Question

※ 引述《[e-mail] (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


> -------------------------------------------------------------------------- <

發信人: [e-mail] (宇恆), 看板: Oversea_Job
標  題: Re: Microsoft Interview Question
發信站: 批踢踢參 (Sun Jan 27 16:11:26 2008)
轉信站: ptt!Group.NCTU!grouppost!Group.NCTU!ptt3

※ 引述《[e-mail] (Sunnyvale)》之銘言：
: ※ 引述《Baudelaire (Sunnyvale)》之銘言：
: : 這題據強者我ebay的朋友說，Google在on-campus也問過他這題。
: 算是quicksort裡面的in-place partition，也不會太難。
: public static int Partition(Ball[] aBalls) {
:     int left = 0, right = aBalls.length - 1;
:     BallColor pivotColor = aBalls[0].Color();
:     while (left <= right) {
:           BallColor leftColor = aBalls[left].Color();
:           BallColor rightColor = aBalls[right].Color();
:           if (leftColor == pivotColor) && rightColor == pivotColor)
:                 left++;
:           } else if (leftColor == pivotColor && rightColor != pivotColor) {
:                 left++;
:           } else if (leftColor != pivotColor && rightColor != pivotColor) {
:                 right--;
:           } else if (leftColor != pivotColor && rightColor == pivotColor) {
:                 Ball tmp = aBalls[left];
:                 aBalls[left] = aBalls[right];
:                 aBalls[right] = tmp;
:                 left++; right--;
:           }
:     }
:     return left;
: }


    直接改Cormen那本書裡的partition似乎可以提供更精簡的答案

    請參考

    Partition(Ball A[])
    {
        i = -1;
        k = A.length - 1;
        x = A[k];
        Ball temp;

        for(j=0; j < k; ++j)
        {
            if(A[j] != x) // Here is the key modification.
            {
               ++i;
               temp = A[i];
               A[i] = A[j];
               A[j] = temp;
            }
        }

        return (i+1);
    }


--
※ 發信站: 批踢踢參(ptt3.cc) 
◆ From: 168.7.230.23