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