n****r
发帖数: 120 | 1 【 以下文字转载自 Topcoders 俱乐部 】
发信人: nibber (nibber), 信区: Topcoders
标 题: 讨论一道老题：分离数组中的正负数
关键字: 算法 数组 O(n) 时间复杂度分析
发信站: BBS 未名空间站 (Thu Nov 8 10:45:04 2012, 美东)
负数在前，正数在后，需要保持负数之间和正数之间的顺序不变！时间复杂度要求O(n)
,空间复杂度O(1)
下面是我的代码，空间复杂度O(1)没问题，时间复杂度分析如下，
设数组中共有负数X个，分散在K个分离的连续负数的子数组段，每个子数组段的长度为
Li，1<=Li
下面算法中K个分离的负数子数组段移到最后位置需要最多进行K次swap操作，而swap的
时间复杂度是O(n)，（这里n是子数段的长度），因此
一共的需要的时间是O(L1)+O(L2)+...+O(Lk) = O(X).因此整体的时间复杂度就是O(n)
这个分析妥不妥？请大牛们给指点一下，还有其他的时间O(n),空间O(1)解法没有？
public static void split(int[] a){
if (a == null || a.length <= 1) return;
int i = 0, j = 0;
while (i
i++;
}
j = i+1;
while (j
while (j=0){
j++;
}
if (j >= a.length) break;
int m = j;
while (j
j++;
}
swap(a, i, m, j-1);
i += j - m;
}
}
private static void swap(int[] a, int l, int m, int r){
reverse(a, l, m-1);
reverse(a, m, r);
reverse(a, l, r);
}
private static void reverse(int[] a, int l, int r){
while (l < r){
int tmp = a[l]; a[l] = a[r]; a[r] = tmp;
l++; r--;
}
} |
b*****u
发帖数: 648 | |
s*****s
发帖数: 157 | |
l*******b
发帖数: 2586 | 4 你确定这个是O(n)? 最坏情况是in place unshuffle 吧。
n)
【在 n****r 的大作中提到】
: 【 以下文字转载自 Topcoders 俱乐部 】
: 发信人: nibber (nibber), 信区: Topcoders
: 标 题: 讨论一道老题：分离数组中的正负数
: 关键字: 算法 数组 O(n) 时间复杂度分析
: 发信站: BBS 未名空间站 (Thu Nov 8 10:45:04 2012, 美东)
: 负数在前，正数在后，需要保持负数之间和正数之间的顺序不变！时间复杂度要求O(n)
: ,空间复杂度O(1)
: 下面是我的代码，空间复杂度O(1)没问题，时间复杂度分析如下，
: 设数组中共有负数X个，分散在K个分离的连续负数的子数组段，每个子数组段的长度为
: Li，1<=Li
|
D**f
发帖数: 439 | 5 假想在数组结尾append一个0，作为pivot，然后以此作quick sort 的partition步骤。
其实append那步可以省略。 |
d**********x
发帖数: 4083 | 6 我觉得这题目比较natural的想法是前后各用一个指针往中间扫描
当然快排有一种partition也是这么做的。。。恩。。。
【在 D**f 的大作中提到】
: 假想在数组结尾append一个0，作为pivot，然后以此作quick sort 的partition步骤。
: 其实append那步可以省略。
|
S********t
发帖数: 3431 | 7 我觉得做不到。记忆有点模糊了，三年前我查过，有论文讨论这个题的一个特殊情况，
很不容易才做到了时间n 空间1
n)
【在 n****r 的大作中提到】
: 【 以下文字转载自 Topcoders 俱乐部 】
: 发信人: nibber (nibber), 信区: Topcoders
: 标 题: 讨论一道老题：分离数组中的正负数
: 关键字: 算法 数组 O(n) 时间复杂度分析
: 发信站: BBS 未名空间站 (Thu Nov 8 10:45:04 2012, 美东)
: 负数在前，正数在后，需要保持负数之间和正数之间的顺序不变！时间复杂度要求O(n)
: ,空间复杂度O(1)
: 下面是我的代码，空间复杂度O(1)没问题，时间复杂度分析如下，
: 设数组中共有负数X个，分散在K个分离的连续负数的子数组段，每个子数组段的长度为
: Li，1<=Li
|
d*s
发帖数: 699 | 8 如果没有0的话这个方法很容易就出来了吧，有什么问题么？
【在 d**********x 的大作中提到】
: 我觉得这题目比较natural的想法是前后各用一个指针往中间扫描
: 当然快排有一种partition也是这么做的。。。恩。。。
|
l*******b
发帖数: 2586 | 9 这一条: 需要保持负数之间和正数之间的顺序不变！
【在 d*s 的大作中提到】
: 如果没有0的话这个方法很容易就出来了吧，有什么问题么？
|
q****m
发帖数: 177 | 10 qick sort 里的partition 做不到 preserve order 吧
【在 D**f 的大作中提到】
: 假想在数组结尾append一个0，作为pivot，然后以此作quick sort 的partition步骤。
: 其实append那步可以省略。
|
|
|
n****r
发帖数: 120 | 11 快排或选择排序是不稳定的，没有办法保持相对顺序！
这题也是我在版上看到的，但没有找到正解！也许时间复杂度要求O(n)
,空间复杂度O(1)做不到！偶仅仅想到O(n^2)的解。 |
b*****u
发帖数: 648 | 12
所谓不稳定是说相等的数字一个被选中pivot后相对于其他几个的位置不定吧
如果数组里没有0，那么添个0进去作pivot 快排一轮还是不稳定的吗？
【在 n****r 的大作中提到】
: 快排或选择排序是不稳定的，没有办法保持相对顺序！
: 这题也是我在版上看到的，但没有找到正解！也许时间复杂度要求O(n)
: ,空间复杂度O(1)做不到！偶仅仅想到O(n^2)的解。
|
e******o
发帖数: 757 | 13 quicksort 需要前面的后面的swap, 是不稳定的
【在 b*****u 的大作中提到】
:
: 所谓不稳定是说相等的数字一个被选中pivot后相对于其他几个的位置不定吧
: 如果数组里没有0，那么添个0进去作pivot 快排一轮还是不稳定的吗？
|
b*****u
发帖数: 648 | 14
这个题里都是正负数swap，正数之间，负数之间并没有swap啊
【在 e******o 的大作中提到】
: quicksort 需要前面的后面的swap, 是不稳定的
|
l*******b
发帖数: 2586 | 15 -1 4 5 -2
按quicksort就变
-1 -2 5 4
啦，哈哈
【在 b*****u 的大作中提到】
:
: 这个题里都是正负数swap，正数之间，负数之间并没有swap啊
|
b*****u
发帖数: 648 | 16 这个反例好，谢谢！
那如果记录一下5的位置，最后shuffle一道能不能解决问题呢？
也就是说，快排在这里带来的所有不稳定性，都是最后一串连续正数没参与swap带来的
，所以只要track这个位置就好了
【在 l*******b 的大作中提到】
: -1 4 5 -2
: 按quicksort就变
: -1 -2 5 4
: 啦，哈哈
|
