b*******h
发帖数: 53 | 1 1. 一个array当中，每个element都是一个带一种颜色的小球。有20种颜色的选择。排
序，将相同颜色的小球放在一起。 要求linear time and in-place.
in-place, 我的理解就是不能再用一个array装重新的排序的小球。
2.如何判断两个矩形overlap. 用最少的判断条件。
这道题是一道经典题吧，隐约好像以前见过。
自己给出的方案： 分别判断两边有没有overlap，就是x方向和y方向的线段有没有重叠
的部分，如果两个方向都有的话，两个矩形overlap。
不知道有没有其他方法。 |
r*******y
发帖数: 1081 | 2 1, construct a hash table of size 20 firstly to find the interval of
one color balls in the sorted array ?
【在 b*******h 的大作中提到】
: 1. 一个array当中，每个element都是一个带一种颜色的小球。有20种颜色的选择。排
: 序，将相同颜色的小球放在一起。 要求linear time and in-place.
: in-place, 我的理解就是不能再用一个array装重新的排序的小球。
: 2.如何判断两个矩形overlap. 用最少的判断条件。
: 这道题是一道经典题吧，隐约好像以前见过。
: 自己给出的方案： 分别判断两边有没有overlap，就是x方向和y方向的线段有没有重叠
: 的部分，如果两个方向都有的话，两个矩形overlap。
: 不知道有没有其他方法。
|
g**e
发帖数: 6127 | 3 1. http://en.wikipedia.org/wiki/Dutch_national_flag_problem
2. check programing interview exposed
【在 b*******h 的大作中提到】
: 1. 一个array当中，每个element都是一个带一种颜色的小球。有20种颜色的选择。排
: 序，将相同颜色的小球放在一起。 要求linear time and in-place.
: in-place, 我的理解就是不能再用一个array装重新的排序的小球。
: 2.如何判断两个矩形overlap. 用最少的判断条件。
: 这道题是一道经典题吧，隐约好像以前见过。
: 自己给出的方案： 分别判断两边有没有overlap，就是x方向和y方向的线段有没有重叠
: 的部分，如果两个方向都有的话，两个矩形overlap。
: 不知道有没有其他方法。
|
b*******h
发帖数: 53 | 4 thanks, great help.
【在 g**e 的大作中提到】
: 1. http://en.wikipedia.org/wiki/Dutch_national_flag_problem
: 2. check programing interview exposed
|
g**e
发帖数: 6127 | 5 a little more info for q2:
using dot product is easier than checking vertices I think
http://stackoverflow.com/questions/115426/algorithm-to-detect-i
http://en.wikipedia.org/wiki/Separating_axis_theorem
【在 b*******h 的大作中提到】
: thanks, great help.
|
f****4
发帖数: 1359 | 6 q1 难道要多次调用Dutch_national_flag_problem？
【在 g**e 的大作中提到】
: 1. http://en.wikipedia.org/wiki/Dutch_national_flag_problem
: 2. check programing interview exposed
|
g**e
发帖数: 6127 | 7 理论上说是可以，但是代码会非常复杂
有什么更好的idea吗？
【在 f****4 的大作中提到】
: q1 难道要多次调用Dutch_national_flag_problem？
|
g***s
发帖数: 3811 | 8 no.
scan once, use 20 variables to count each color. (n)
Then use 20 pointers and in-place swap to scan. (n*2) -- similar with the
algo to swap k to kth. but here swap k to k-th block.
space O(20)
【在 f****4 的大作中提到】
: q1 难道要多次调用Dutch_national_flag_problem？
|
g**********y
发帖数: 14569 | 9 代码不复杂吧。反正固定20种颜色，每种都往头上换，不停挪指针，复杂度还是O(N)。
【在 g**e 的大作中提到】
: 理论上说是可以，但是代码会非常复杂
: 有什么更好的idea吗？
|
s*****y
发帖数: 897 | 10 我还以为不可以申请额外空间呢。
【在 g***s 的大作中提到】
: no.
: scan once, use 20 variables to count each color. (n)
: Then use 20 pointers and in-place swap to scan. (n*2) -- similar with the
: algo to swap k to kth. but here swap k to k-th block.
: space O(20)
|
|
|
g***s
发帖数: 3811 | 11 O(20), can be thought as O(1).
any algo needs extra variables.
【在 s*****y 的大作中提到】
: 我还以为不可以申请额外空间呢。
|
g**e
发帖数: 6127 | 12 不得20个case switch吗
【在 g**********y 的大作中提到】
: 代码不复杂吧。反正固定20种颜色，每种都往头上换，不停挪指针，复杂度还是O(N)。
|
g**********y
发帖数: 14569 | 13 颜色应该存在给定数组里，可以假设已经排好序了。我想这些都是枝节问题，面试官不
在乎的。
【在 g**e 的大作中提到】
: 不得20个case switch吗
|
f****4
发帖数: 1359 | 14 抛个没有count的；一次写对还是有难度的
grass的count的办法能简化代码
#include
int k = 0;
int pts[k+1]; //pts[0] for color 1; pts[k-1] for color k; pts[k] is the
current index in balls
void printArray(int *arr, int length)
{
for(int i = 0; i < length; i++)
printf("%d,",arr[i]);
printf("\n");
}
void KquickSortPartition(int *arr, int length)
{
if (arr == NULL || length == 0 || k <= 0) return;
printArray(arr, length);
for (int i = 0; i < k+1; i++)
pts[i] = 0;
int ball;
int color;
while (pts[k]< length)
{
// current color
color = arr[pts[k]];
for (int j = k; j > color; j--)
{
ball = arr[pts[j]];
arr[pts[j]] = arr[pts[j-1]];
arr[pts[j-1]] = ball;
}
for (int j = color; j <= k; j++)
pts[j]+=1;
// printArray(pts, k+1);
}
printArray(arr, length);
printf("\n");
}
int main ()
{
k = 4;
int balls1[] = {1,1,2,4,1,2,1,2,4,4,4,2,3,4,3,4,3,4,2,3,4,2,3,3,4,1};
KquickSortPartition(balls1, sizeof(balls1)/sizeof(int));
int balls2[] = {3,3,3,3,3,1,1,1,4,4,4,4};
KquickSortPartition(balls2, sizeof(balls2)/sizeof(int));
int balls3[] = {1,1,1};
KquickSortPartition(balls3, sizeof(balls3)/sizeof(int));
int balls4[] = {4,4,4};
KquickSortPartition(balls4, sizeof(balls4)/sizeof(int));
int balls5[] = {1,2,3,4,1,2,3,4,1,2,3,4};
KquickSortPartition(balls5, sizeof(balls5)/sizeof(int));
k = 1;
int balls6[] = {1,1,1,1,1};
KquickSortPartition(balls6, sizeof(balls6)/sizeof(int));
} |
d*******d
发帖数: 2050 | 15 我认为用hash数个数再放回去是正解.
【在 r*******y 的大作中提到】
: 1, construct a hash table of size 20 firstly to find the interval of
: one color balls in the sorted array ?
|
g***s
发帖数: 3811 | 16 This codes are not O(N).
【在 f****4 的大作中提到】
: 抛个没有count的；一次写对还是有难度的
: grass的count的办法能简化代码
: #include
: int k = 0;
: int pts[k+1]; //pts[0] for color 1; pts[k-1] for color k; pts[k] is the
: current index in balls
: void printArray(int *arr, int length)
: {
: for(int i = 0; i < length; i++)
: printf("%d,",arr[i]);
|
d*******d
发帖数: 2050 | 17 第二题可没说这两矩形平行于坐标轴阿
【在 b*******h 的大作中提到】
: 1. 一个array当中，每个element都是一个带一种颜色的小球。有20种颜色的选择。排
: 序，将相同颜色的小球放在一起。 要求linear time and in-place.
: in-place, 我的理解就是不能再用一个array装重新的排序的小球。
: 2.如何判断两个矩形overlap. 用最少的判断条件。
: 这道题是一道经典题吧，隐约好像以前见过。
: 自己给出的方案： 分别判断两边有没有overlap，就是x方向和y方向的线段有没有重叠
: 的部分，如果两个方向都有的话，两个矩形overlap。
: 不知道有没有其他方法。
|
g***s
发帖数: 3811 | 18 public class ColorBalls {
public static void arrange(int[] balls, int colorNum){
int[] count = new int[colorNum];
int[] pointers = new int[colorNum];
//count color
for (int color : balls) count[color]++;
//set the pointers
for (int i=0;i
pointers[i+1] += pointers[i] + count[i];
}
int currentColor = 0;
int c = count[currentColor];
for (int pos=0;pos
if (c==0){
c = count[++currentColor];
continue;
}
if (balls[pos]!=currentColor){
swap(balls, pos, pointers[balls[pos]]++);
} else {
pos++;c--;
}
}
}
private static void swap(int[] balls, int p1, int p2) {
int t = balls[p1];
balls[p1] = balls[p2];
balls[p2] = t;
}
public static void main(String[] args) {
final int N = 100;
final int COLOR_NUM = 20;
int[] balls = new int[N];
Random random = new Random() ;
for (int i=0;i
random.nextInt(COLOR_NUM);
arrange(balls,COLOR_NUM);
System.out.println(Arrays.toString(balls));
}
}
the
【在 g***s 的大作中提到】
: no.
: scan once, use 20 variables to count each color. (n)
: Then use 20 pointers and in-place swap to scan. (n*2) -- similar with the
: algo to swap k to kth. but here swap k to k-th block.
: space O(20)
|
g***s
发帖数: 3811 | 19 check gate's posts.
【在 d*******d 的大作中提到】
: 第二题可没说这两矩形平行于坐标轴阿
|
f****4
发帖数: 1359 | 20 这里最坏是O(kN)
k=20的时候，不能认为是 O(N)?
【在 g***s 的大作中提到】
: This codes are not O(N).
|
|
|
g***s
发帖数: 3811 | 21 oh. yes, you are right.
but we can finish it in O(3*N).
【在 f****4 的大作中提到】
: 这里最坏是O(kN)
: k=20的时候，不能认为是 O(N)?
|
f****4
发帖数: 1359 | 22 恩，用count是简单很多
我那个是上次看到有人给问到类似问题，但要求in-place, O(N)并且不允许用count的
办法，才写的
【在 g***s 的大作中提到】
: oh. yes, you are right.
: but we can finish it in O(3*N).
|
g**********y
发帖数: 14569 | 23 如果用count的话，count完为什么不直接赋值？反正都是整数。 |
g***s
发帖数: 3811 | 24 Since it could be a Node inlcuding other fields.
【在 g**********y 的大作中提到】
: 如果用count的话，count完为什么不直接赋值？反正都是整数。
|
d*******d
发帖数: 2050 | 25 其实你那个和count是一码事,只不过count的内容变了一点而已.
【在 f****4 的大作中提到】
: 恩，用count是简单很多
: 我那个是上次看到有人给问到类似问题，但要求in-place, O(N)并且不允许用count的
: 办法，才写的
|
f****4
发帖数: 1359 | 26 你是指都用了k个指针的插入？
count直接把每个指针所在的位置放好了
我的k个指针都是从0开始的
【在 d*******d 的大作中提到】
: 其实你那个和count是一码事,只不过count的内容变了一点而已.
|
w*****3
发帖数: 101 | 27 counting 以后直接填似乎简单一点
int[] cntAry = new int[21];
public int[] solve(int[] bary) {
for (int v : bary) {
cntAry[v]++;
}
int tmp = 0, total = 0;
for (int i = 0; i < cntAry.length; ++i) {
tmp = cntAry[i];
cntAry[i] = total;
total += tmp;
}
for(int i = 0; i< cntAry.length - 1; ++i){
for(int j = cntAry[i]; j < cntAry[i+1]; ++j){
bary[j] = i;
}
}
return bary;
} |
g***s
发帖数: 3811 | 28 This is not general solution,since the ball Node could have more fields.
【在 w*****3 的大作中提到】
: counting 以后直接填似乎简单一点
: int[] cntAry = new int[21];
: public int[] solve(int[] bary) {
: for (int v : bary) {
: cntAry[v]++;
: }
: int tmp = 0, total = 0;
:
: for (int i = 0; i < cntAry.length; ++i) {
: tmp = cntAry[i];
|
w*****3
发帖数: 101 | |
