j*****r
发帖数: 57 | 1 有红黄蓝三种颜色的球各N个, 一共3N个球, 次序任意. 只通过操作exchange(i, j),
如何排列成 "红黄蓝红黄蓝红黄蓝..." 的顺序?
解法已有, 但想看看大家的想法. | a**********s
发帖数: 588 | 2 // Say you have the following
typedef enum {
red,
yellow,
blue
} Color;
const Color expectedColors[] = {Red, Yellow, Blue};
// The main loop should be something like:
for (int i = 0; i < 3N; i++) {
Color expectedColor = expectedColors[i%3];
if (getColor(i) != expectedColor) {
exchange(i, findNext(i+1, expectedColor));
}
}
int findNext(int start, Color expectedColor) {
while(getColor[start++] != expectedColor);
return start;
}
【在 j*****r 的大作中提到】
: 有红黄蓝三种颜色的球各N个, 一共3N个球, 次序任意. 只通过操作exchange(i, j),
: 如何排列成 "红黄蓝红黄蓝红黄蓝..." 的顺序?
: 解法已有, 但想看看大家的想法.
| j*****r
发帖数: 57 | 3 这样的话, 相当于选择排序. 复杂度是O(N^2).
这问题有O(N)时间的in-place算法. 我当时想到解法, 但是写代码时加入一些防止越界
的条件判断, 代码显得冗余. 回来整理出代码, 做了测试.
不过我想知道别人在没有见过这问题的情况下, 多长时间能写出正确解答来.
【在 a**********s 的大作中提到】
: // Say you have the following
: typedef enum {
: red,
: yellow,
: blue
: } Color;
: const Color expectedColors[] = {Red, Yellow, Blue};
: // The main loop should be something like:
: for (int i = 0; i < 3N; i++) {
: Color expectedColor = expectedColors[i%3];
| q****m
发帖数: 177 | 4 感觉可以先sort 三色旗
【在 j*****r 的大作中提到】
: 有红黄蓝三种颜色的球各N个, 一共3N个球, 次序任意. 只通过操作exchange(i, j),
: 如何排列成 "红黄蓝红黄蓝红黄蓝..." 的顺序?
: 解法已有, 但想看看大家的想法.
| j*****r
发帖数: 57 | 5 呵呵, 我当时也先想到sort三色旗. 面试官还让我解释了一下三色旗算法.
不过, 先排成RRR..GGG..BBB.., 要再排成RGBRGBRGB..似乎不容易.
【在 q****m 的大作中提到】
: 感觉可以先sort 三色旗
| H*****l
发帖数: 1257 | 6 sort的话in place只用exchange（i,j)有复杂度O(N)的方法么
【在 j*****r 的大作中提到】
: 呵呵, 我当时也先想到sort三色旗. 面试官还让我解释了一下三色旗算法.
: 不过, 先排成RRR..GGG..BBB.., 要再排成RGBRGBRGB..似乎不容易.
| o***g
发帖数: 2784 | 7 排序和排成题目要求的顺序是一样的
特点是你事先知道每个位置应该是什么颜色的。
跟排数（int）是不一样的，因为拿到一个数你不知道这个数应该在哪儿。
解法是，安排3个指针，分别指向下一个没排好的颜色的地方，开始坐标是0 1 2
然后循环，可以一个颜色一个颜色循环，也可以大家一起循环。
拿到位置的球，如果这个位置就应该放这个球，就看下一个。
如果这个球的位置放的是别的颜色的，就把这个球和这个球该放的地方的球换一下，被
交换的地方的指针往下移。这样这个位置不一定好了，但是被交换的位置肯定好了。下
次循环还看当前位置是什么颜色的球。所以，每次循环都有一个位置颜色是对的。一共
还是需要3N次就好了。
【在 j*****r 的大作中提到】
: 呵呵, 我当时也先想到sort三色旗. 面试官还让我解释了一下三色旗算法.
: 不过, 先排成RRR..GGG..BBB.., 要再排成RGBRGBRGB..似乎不容易.
| j*****r
发帖数: 57 | 8 算法的确如此.
不知道这个题的出处是哪里.
【在 o***g 的大作中提到】
: 排序和排成题目要求的顺序是一样的
: 特点是你事先知道每个位置应该是什么颜色的。
: 跟排数（int）是不一样的，因为拿到一个数你不知道这个数应该在哪儿。
: 解法是，安排3个指针，分别指向下一个没排好的颜色的地方，开始坐标是0 1 2
: 然后循环，可以一个颜色一个颜色循环，也可以大家一起循环。
: 拿到位置的球，如果这个位置就应该放这个球，就看下一个。
: 如果这个球的位置放的是别的颜色的，就把这个球和这个球该放的地方的球换一下，被
: 交换的地方的指针往下移。这样这个位置不一定好了，但是被交换的位置肯定好了。下
: 次循环还看当前位置是什么颜色的球。所以，每次循环都有一个位置颜色是对的。一共
: 还是需要3N次就好了。
| f****8
发帖数: 33 | 9 楼上的算法比较清晰，但是因为EXCHANGE的COST高于SCAN的COST，而这种算法里面
EXCHANGE的次数多了一些，可以做一些优化：
1. 针对三种颜色保存其分别在findNext中返回的位置（start[color]），并将start[
color]+1作为下次搜索的起始点；
2. 在findNext中，如果找到的下一个颜色原本就在其最终应该呆的位置上，就跳过它
，找到一个“放错位置”的该颜色的球。
【在 a**********s 的大作中提到】
: // Say you have the following
: typedef enum {
: red,
: yellow,
: blue
: } Color;
: const Color expectedColors[] = {Red, Yellow, Blue};
: // The main loop should be something like:
: for (int i = 0; i < 3N; i++) {
: Color expectedColor = expectedColors[i%3];
| w****r
发帖数: 28 | 10 先排红的， 第k个红的和位置 3k的球交换
拍黄的， 第k个黄的和位置 3k+1的球交换 | | | j*****r
发帖数: 57 | 11 algorithmics的算法也可以, 不过是O(N^2).
orang的算法是O(N).
【在 f****8 的大作中提到】
: 楼上的算法比较清晰，但是因为EXCHANGE的COST高于SCAN的COST，而这种算法里面
: EXCHANGE的次数多了一些，可以做一些优化：
: 1. 针对三种颜色保存其分别在findNext中返回的位置（start[color]），并将start[
: color]+1作为下次搜索的起始点；
: 2. 在findNext中，如果找到的下一个颜色原本就在其最终应该呆的位置上，就跳过它
: ，找到一个“放错位置”的该颜色的球。
| j*****r
发帖数: 57 | 12 差不多. 你知道这个问题的来源吗?
【在 w****r 的大作中提到】
: 先排红的， 第k个红的和位置 3k的球交换
: 拍黄的， 第k个黄的和位置 3k+1的球交换
| o***g
发帖数: 2784 | 13 不知道出处
【在 j*****r 的大作中提到】
: 算法的确如此.
: 不知道这个题的出处是哪里.
| w****r
发帖数: 28 | 14 一起循环似乎不可以，需要一个颜色一个颜色来， 而且只需要排2个颜色就可以了
color = ["B", "R", "R", "R", "B", "B", "G", "G", "G"]
def exchange(color, i, j):
temp = color[i]
color[i] = color[j]
color[j] = temp
def arrange(color, c, pos):
j = pos
for k in range(len(color)):
if ((color[k] == c) & (k%3 != pos)):
while (color[j] == c):
j += 3
exchange(color, k, j)
arrange(color, "R", 0)
arrange(color, "G", 1)
【在 o***g 的大作中提到】
: 排序和排成题目要求的顺序是一样的
: 特点是你事先知道每个位置应该是什么颜色的。
: 跟排数（int）是不一样的，因为拿到一个数你不知道这个数应该在哪儿。
: 解法是，安排3个指针，分别指向下一个没排好的颜色的地方，开始坐标是0 1 2
: 然后循环，可以一个颜色一个颜色循环，也可以大家一起循环。
: 拿到位置的球，如果这个位置就应该放这个球，就看下一个。
: 如果这个球的位置放的是别的颜色的，就把这个球和这个球该放的地方的球换一下，被
: 交换的地方的指针往下移。这样这个位置不一定好了，但是被交换的位置肯定好了。下
: 次循环还看当前位置是什么颜色的球。所以，每次循环都有一个位置颜色是对的。一共
: 还是需要3N次就好了。
| j*****r
发帖数: 57 | 15 一个颜色一个颜色的确排2个颜色, 剩下的颜色就也对了.
一起循环也可以, 我有代码, 而且用所有全排列测试过. 可能的情况应该是:
N permutations
----------------
1 6
2 90
3 1679
4 34650
【在 w****r 的大作中提到】
: 一起循环似乎不可以，需要一个颜色一个颜色来， 而且只需要排2个颜色就可以了
: color = ["B", "R", "R", "R", "B", "B", "G", "G", "G"]
: def exchange(color, i, j):
: temp = color[i]
: color[i] = color[j]
: color[j] = temp
: def arrange(color, c, pos):
: j = pos
: for k in range(len(color)):
: if ((color[k] == c) & (k%3 != pos)):
| j*******u
发帖数: 10 | 16 这个跟Leetcode上那道sort color是基本一样的吧.. | j*****r
发帖数: 57 | 17 mm, 这个满不一样.
【在 j*******u 的大作中提到】
: 这个跟Leetcode上那道sort color是基本一样的吧..
| j*******u
发帖数: 10 | 18 啊，是呢，尴尬，没好好看题... :)
【在 j*****r 的大作中提到】
: mm, 这个满不一样.
| a**********s
发帖数: 588 | 19 这个很简单，findNext(i, expectedColor)的调用稍微改变一下：
// The start indices where we should look for a particular color:
int lookupIndices[] = {-1, -1, -1};
// The main loop should be something like:
for (int i = 0; i < 3N; i++) {
Color expectedColor = expectedColors[i%3];
if (getColor(i) != expectedColor) {
int indexOfExpected = findNext(
max(lookupIndices[expectedColor], i+1),
expectedColor);
exchange(i, indexOfExpected);
lookupIndices[expectedColor] = indexOfExpected + 1;
}
}
【在 j*****r 的大作中提到】
: 这样的话, 相当于选择排序. 复杂度是O(N^2).
: 这问题有O(N)时间的in-place算法. 我当时想到解法, 但是写代码时加入一些防止越界
: 的条件判断, 代码显得冗余. 回来整理出代码, 做了测试.
: 不过我想知道别人在没有见过这问题的情况下, 多长时间能写出正确解答来.
| j*****r
发帖数: 57 | 20 这个没有什么变化吧, 和刚才的算法差不多.
而且findNext()不是必要的, 直接用lookupIndices[expectedColor]就可以.
【在 a**********s 的大作中提到】
: 这个很简单，findNext(i, expectedColor)的调用稍微改变一下：
: // The start indices where we should look for a particular color:
: int lookupIndices[] = {-1, -1, -1};
: // The main loop should be something like:
: for (int i = 0; i < 3N; i++) {
: Color expectedColor = expectedColors[i%3];
: if (getColor(i) != expectedColor) {
: int indexOfExpected = findNext(
: max(lookupIndices[expectedColor], i+1),
: expectedColor);
| | | m******e
发帖数: 82 | 21 先三色旗，再RGBRGB...可以的吧
从RRRRGGGGBBBB变到RGBRGBRGBRGB可以这样：
RRRRGGGGBBBB=>
RGRRRGGGBBBB=>
RGBRRGGGRBBB=>
RGBRRRGGGBBB
【在 j*****r 的大作中提到】
: 呵呵, 我当时也先想到sort三色旗. 面试官还让我解释了一下三色旗算法.
: 不过, 先排成RRR..GGG..BBB.., 要再排成RGBRGBRGB..似乎不容易.
| T*****u
发帖数: 7103 | 22 就是sort吧，三个指针，总指针，红指针，黄指针，总指针不能动红指针黄指针动过的
，从头开始扫，把红得放到k*3,黄的放到1+k*3，扫倒头就好了。 | a**********s
发帖数: 588 | 23 再想想
【在 j*****r 的大作中提到】
: 这个没有什么变化吧, 和刚才的算法差不多.
: 而且findNext()不是必要的, 直接用lookupIndices[expectedColor]就可以.
| j*****r
发帖数: 57 | 24 对, 这也可以. 算法代码已经测试通过了.
【在 m******e 的大作中提到】
: 先三色旗，再RGBRGB...可以的吧
: 从RRRRGGGGBBBB变到RGBRGBRGBRGB可以这样：
: RRRRGGGGBBBB=>
: RGRRRGGGBBBB=>
: RGBRRGGGRBBB=>
: RGBRRRGGGBBB
| l****h
发帖数: 1189 | 25 这个题目的来源就是荷兰旗问题吧。
做荷兰旗swap的时候,保持直接插到从尾巴倒回去走的正确位置.
【在 j*****r 的大作中提到】
: 对, 这也可以. 算法代码已经测试通过了.
|
|
