i***0
发帖数: 37 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: iq300 (iq300), 信区: JobHunting
标 题: Partitioning
发信站: BBS 未名空间站 (Wed Mar 5 17:27:35 2008)
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 | h****e
发帖数: 2125 | 2 这题不就是in-place sorting么，RED相当于0，BLUE相当于1。
write
matter
function
【在 i***0 的大作中提到】
: 【 以下文字转载自 JobHunting 讨论区 】
: 发信人: iq300 (iq300), 信区: JobHunting
: 标 题: Partitioning
: 发信站: BBS 未名空间站 (Wed Mar 5 17:27:35 2008)
: 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
| c*****t
发帖数: 1879 | 3 You don't even need sorting, which would be O (nlogn). Simple
counting + swapping would be enough (O (n)).
【在 h****e 的大作中提到】
: 这题不就是in-place sorting么，RED相当于0，BLUE相当于1。
:
: write
: matter
: function
|
|
