※ 引述《Baudelaire (Sunnyvale)》之銘言：
: 這題據強者我ebay的朋友說，Google在on-campus也問過他這題。
: Array Rotation
: You should be able to do this in less than linear time.
: Implement the following function, FindSortedArrayRotation,
: which takes as its input an array of unique integers that has
: been sorted in ascending order, then rotated by an unknown
: amount X where 0 <= X <= (arrayLength - 1). An array rotation
: by amount X moves every element array[i] to array[(i + X) %
: arrayLength]. FindSortedArrayRotation discovers and returns X
: by examining the array. Consider performance, memory utilization
: and code clarity and elegance of the solution when implementing
: the function.
基本上算是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;
}
: ----
: Partitioning
: Given an array of balls, which can be one of two colors (RED or BLUE),
: write a function that partitions the array in-place such that on exit
: from the function all the balls of the same color are contiguous. It
: does not matter whether the red or blue balls come first. The return
: value from the function is the index of the first ball of the second
: color. If there is only one color of balls in the array then the
: return value should be 0. It is not legal to change the color of a
: ball. They must be moved. Consider performance, memory utilization
: and code clarity and elegance of the solution when implementing the
: function.
算是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;
}
--
Je t'aime,o capitale infame.
Tu m'as donne ta boue et j'en ai fait de l'or.
Charles Baudelaire 1821-67
http://wonderfultown.spaces.live.com/
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 76.21.111.81