从水木上看到个数组题# JobHunting - 待字闺中
c*p
1 楼
一个未排序整数数组，有正负数，重新排列使负数排在正数前面，并且要求不改变原来
的相对顺序
比如：
input:
1,7,-5,9,-12,15
ans: -5,-12,1,7,9,15
要求时间复杂度O(N),空间O(1)
的相对顺序
比如：
input:
1,7,-5,9,-12,15
ans: -5,-12,1,7,9,15
要求时间复杂度O(N),空间O(1)
f*t
2 楼
只能想到一个类似于bubble sort的解法，时间复杂度是O(N^2)...
g*k
3 楼
只能想到O(nlgn)的stable 算法，O(n)的没啥思路
【在 c****p 的大作中提到】
: 一个未排序整数数组，有正负数，重新排列使负数排在正数前面，并且要求不改变原来
: 的相对顺序
: 比如：
: input:
: 1,7,-5,9,-12,15
: ans: -5,-12,1,7,9,15
: 要求时间复杂度O(N),空间O(1)
【在 c****p 的大作中提到】
: 一个未排序整数数组，有正负数，重新排列使负数排在正数前面，并且要求不改变原来
: 的相对顺序
: 比如：
: input:
: 1,7,-5,9,-12,15
: ans: -5,-12,1,7,9,15
: 要求时间复杂度O(N),空间O(1)
b*r
4 楼
扫两边？
void reorder(int input[]){
int length=sizeof(input)/sizeof(int);
int output[length];
int last_negative_index=-1;
int i=0;
for (i=0; i
{
last_negative_index++;
// move this number before all the positive numbers.
output[last_negative_index]=input[i];
}
}
// now we have last_negative_index
for (i=0; i
output[last_negative_index+1]=input[i];
last_negetive_index++;
}
}
}
【在 c****p 的大作中提到】
: 一个未排序整数数组，有正负数，重新排列使负数排在正数前面，并且要求不改变原来
: 的相对顺序
: 比如：
: input:
: 1,7,-5,9,-12,15
: ans: -5,-12,1,7,9,15
: 要求时间复杂度O(N),空间O(1)
void reorder(int input[]){
int length=sizeof(input)/sizeof(int);
int output[length];
int last_negative_index=-1;
int i=0;
for (i=0; i
{
last_negative_index++;
// move this number before all the positive numbers.
output[last_negative_index]=input[i];
}
}
// now we have last_negative_index
for (i=0; i
output[last_negative_index+1]=input[i];
last_negetive_index++;
}
}
}
【在 c****p 的大作中提到】
: 一个未排序整数数组，有正负数，重新排列使负数排在正数前面，并且要求不改变原来
: 的相对顺序
: 比如：
: input:
: 1,7,-5,9,-12,15
: ans: -5,-12,1,7,9,15
: 要求时间复杂度O(N),空间O(1)
g*k
5 楼
O(1) space.
【在 b***r 的大作中提到】
: 扫两边？
: void reorder(int input[]){
: int length=sizeof(input)/sizeof(int);
: int output[length];
:
: int last_negative_index=-1;
: int i=0;
: for (i=0; i
: {
【在 b***r 的大作中提到】
: 扫两边？
: void reorder(int input[]){
: int length=sizeof(input)/sizeof(int);
: int output[length];
:
: int last_negative_index=-1;
: int i=0;
: for (i=0; i
: {
i*e
6 楼
Already found a bug in your code.
--> int length=sizeof(input)/sizeof(int);
This will always set lenght as 1. Because input is an int* pointer that's
passed into the function, therefore sizeof(input) = sizeof(int*) = 4.
【在 b***r 的大作中提到】
: 扫两边？
: void reorder(int input[]){
: int length=sizeof(input)/sizeof(int);
: int output[length];
:
: int last_negative_index=-1;
: int i=0;
: for (i=0; i
: {
--> int length=sizeof(input)/sizeof(int);
This will always set lenght as 1. Because input is an int* pointer that's
passed into the function, therefore sizeof(input) = sizeof(int*) = 4.
【在 b***r 的大作中提到】
: 扫两边？
: void reorder(int input[]){
: int length=sizeof(input)/sizeof(int);
: int output[length];
:
: int last_negative_index=-1;
: int i=0;
: for (i=0; i
: {
r*n
7 楼
需要考虑数值是0的情况么？
另外，如果要求in-place replacement，可以做到时间O(n)，空间O(1)么？
【在 b***r 的大作中提到】
: 扫两边？
: void reorder(int input[]){
: int length=sizeof(input)/sizeof(int);
: int output[length];
:
: int last_negative_index=-1;
: int i=0;
: for (i=0; i
: {
另外，如果要求in-place replacement，可以做到时间O(n)，空间O(1)么？
【在 b***r 的大作中提到】
: 扫两边？
: void reorder(int input[]){
: int length=sizeof(input)/sizeof(int);
: int output[length];
:
: int last_negative_index=-1;
: int i=0;
: for (i=0; i
: {
i*e
8 楼
From the discussions on SO, it seems unlikely there exist a solution with O(
N) time and O(1) space (or maybe it's a research problem). Dutch national
flag sorting can solve this in O(N) time and O(1) space, but is not stable.
http://stackoverflow.com/questions/5347616/how-to-sort-an-integ
N) time and O(1) space (or maybe it's a research problem). Dutch national
flag sorting can solve this in O(N) time and O(1) space, but is not stable.
http://stackoverflow.com/questions/5347616/how-to-sort-an-integ
b*r
9 楼
牛人啊。ｂｏｗ
【在 i**********e 的大作中提到】
: Already found a bug in your code.
: --> int length=sizeof(input)/sizeof(int);
: This will always set lenght as 1. Because input is an int* pointer that's
: passed into the function, therefore sizeof(input) = sizeof(int*) = 4.
【在 i**********e 的大作中提到】
: Already found a bug in your code.
: --> int length=sizeof(input)/sizeof(int);
: This will always set lenght as 1. Because input is an int* pointer that's
: passed into the function, therefore sizeof(input) = sizeof(int*) = 4.
b*g
10 楼
从后往前扫瞄到遇到第一个负数，
把这个负数与它前面的正数交换，直到，它前面也是负数
这样负数慢慢成堆，继续与之前的正数序列交换，直到数组的第一个元素。
比如：
3,4,1,7,-5,9,-12,15
-->
3,4,1,7,-5,-12,9,15
-->
-5，-12，1,7, 3，4，9,15
-->
-5,-12,3，4，1，7,9,15
负数序列和正数序列的交换比较tricky，但是应该是可以保证O(N)的，
以 3,4,1,7,-5,-12 为例
先把-5，-12同正数序列的头两个交换
得到
-5,-12,1,7,3,4,
然后，把，1,7,同3，4交换保证位置：
得到
-5,-12,3,4,1,7,
以此类推。
把m 连续的负数序列 同 之前的 k连续正数序列交换，可以在 m+k时间内完成，
【在 c****p 的大作中提到】
: 一个未排序整数数组，有正负数，重新排列使负数排在正数前面，并且要求不改变原来
: 的相对顺序
: 比如：
: input:
: 1,7,-5,9,-12,15
: ans: -5,-12,1,7,9,15
: 要求时间复杂度O(N),空间O(1)
把这个负数与它前面的正数交换，直到，它前面也是负数
这样负数慢慢成堆，继续与之前的正数序列交换，直到数组的第一个元素。
比如：
3,4,1,7,-5,9,-12,15
-->
3,4,1,7,-5,-12,9,15
-->
-5，-12，1,7, 3，4，9,15
-->
-5,-12,3，4，1，7,9,15
负数序列和正数序列的交换比较tricky，但是应该是可以保证O(N)的，
以 3,4,1,7,-5,-12 为例
先把-5，-12同正数序列的头两个交换
得到
-5,-12,1,7,3,4,
然后，把，1,7,同3，4交换保证位置：
得到
-5,-12,3,4,1,7,
以此类推。
把m 连续的负数序列 同 之前的 k连续正数序列交换，可以在 m+k时间内完成，
【在 c****p 的大作中提到】
: 一个未排序整数数组，有正负数，重新排列使负数排在正数前面，并且要求不改变原来
: 的相对顺序
: 比如：
: input:
: 1,7,-5,9,-12,15
: ans: -5,-12,1,7,9,15
: 要求时间复杂度O(N),空间O(1)
f*4
11 楼
给你个反例
1 -1 2 -2 3 -3 4 -4 5 -5 6 -6
你算一下要交换多少次吧
【在 b**********g 的大作中提到】
: 从后往前扫瞄到遇到第一个负数，
: 把这个负数与它前面的正数交换，直到，它前面也是负数
: 这样负数慢慢成堆，继续与之前的正数序列交换，直到数组的第一个元素。
: 比如：
: 3,4,1,7,-5,9,-12,15
: -->
: 3,4,1,7,-5,-12,9,15
: -->
: -5，-12，1,7, 3，4，9,15
: -->
1 -1 2 -2 3 -3 4 -4 5 -5 6 -6
你算一下要交换多少次吧
【在 b**********g 的大作中提到】
: 从后往前扫瞄到遇到第一个负数，
: 把这个负数与它前面的正数交换，直到，它前面也是负数
: 这样负数慢慢成堆，继续与之前的正数序列交换，直到数组的第一个元素。
: 比如：
: 3,4,1,7,-5,9,-12,15
: -->
: 3,4,1,7,-5,-12,9,15
: -->
: -5，-12，1,7, 3，4，9,15
: -->
p*z
12 楼
我有一个思路，但是没编程！大家讨论一下！
Hint：不知道大家有没有看过reverse the words in a sentence的例子,我简单说一下
I love you => you love I
程序：
1）reverse 每一个单词：I evol uoy
2) reverse 每整个句子： you love I
根据上面的例子，我们可以同理做这个题（我们先简化为只有前负后正）：5，7，9，-
1，-4 （不知道有大家有木有灵感，其实我们可以把上题的空格和这题的正负交界同比）
1） reverse 正和负的sub array： 9，7，5，-4，-1
2） reverse 这两个sub arrays：-1，-4，5，7，9
所以，把上面的例子复杂化： -1，-4，5，7，9，-1231，-123，54，3462
1）reverse 前面两个正和负的sub arrays：-1，-4，9，7，5，-123，-1231，54，
3462
2）reverse 这两个sub arrays：-1，-4，-1231，-123，5，7，9，，54，3462
所以总的来说：找到两个sub arrays 且前面的sub array都是正数，后面的sub array
都是负数就用这种方法来in place地换位置。请高手测评一下！
Hint：不知道大家有没有看过reverse the words in a sentence的例子,我简单说一下
I love you => you love I
程序：
1）reverse 每一个单词：I evol uoy
2) reverse 每整个句子： you love I
根据上面的例子，我们可以同理做这个题（我们先简化为只有前负后正）：5，7，9，-
1，-4 （不知道有大家有木有灵感，其实我们可以把上题的空格和这题的正负交界同比）
1） reverse 正和负的sub array： 9，7，5，-4，-1
2） reverse 这两个sub arrays：-1，-4，5，7，9
所以，把上面的例子复杂化： -1，-4，5，7，9，-1231，-123，54，3462
1）reverse 前面两个正和负的sub arrays：-1，-4，9，7，5，-123，-1231，54，
3462
2）reverse 这两个sub arrays：-1，-4，-1231，-123，5，7，9，，54，3462
所以总的来说：找到两个sub arrays 且前面的sub array都是正数，后面的sub array
都是负数就用这种方法来in place地换位置。请高手测评一下！
c*p
13 楼
这个可行，我在贴题的时候也想到了,但是应该不是O(N)
给定这样一个数列：
1 -1 2 -2 3 -3 4 -4 ... N/2 -N/2
这个已经是O(N^2)了。
，-
比）
【在 p****z 的大作中提到】
: 我有一个思路，但是没编程！大家讨论一下！
: Hint：不知道大家有没有看过reverse the words in a sentence的例子,我简单说一下
: I love you => you love I
: 程序：
: 1）reverse 每一个单词：I evol uoy
: 2) reverse 每整个句子： you love I
: 根据上面的例子，我们可以同理做这个题（我们先简化为只有前负后正）：5，7，9，-
: 1，-4 （不知道有大家有木有灵感，其实我们可以把上题的空格和这题的正负交界同比）
: 1） reverse 正和负的sub array： 9，7，5，-4，-1
: 2） reverse 这两个sub arrays：-1，-4，5，7，9
给定这样一个数列：
1 -1 2 -2 3 -3 4 -4 ... N/2 -N/2
这个已经是O(N^2)了。
，-
比）
【在 p****z 的大作中提到】
: 我有一个思路，但是没编程！大家讨论一下！
: Hint：不知道大家有没有看过reverse the words in a sentence的例子,我简单说一下
: I love you => you love I
: 程序：
: 1）reverse 每一个单词：I evol uoy
: 2) reverse 每整个句子： you love I
: 根据上面的例子，我们可以同理做这个题（我们先简化为只有前负后正）：5，7，9，-
: 1，-4 （不知道有大家有木有灵感，其实我们可以把上题的空格和这题的正负交界同比）
: 1） reverse 正和负的sub array： 9，7，5，-4，-1
: 2） reverse 这两个sub arrays：-1，-4，5，7，9
b*8
14 楼
就目前看到的很多例子，N时间1空间还要Inpace+Stable，一般很难同时满足，多数都
是少任何一个要求都行。
是少任何一个要求都行。
g*o
15 楼
One method I can think of is scanning once to find how many positive and
negative numbers are. Then scan second time and put every number is its
correct final position. This should be O(N) and O(1)
【在 c****p 的大作中提到】
: 一个未排序整数数组，有正负数，重新排列使负数排在正数前面，并且要求不改变原来
: 的相对顺序
: 比如：
: input:
: 1,7,-5,9,-12,15
: ans: -5,-12,1,7,9,15
: 要求时间复杂度O(N),空间O(1)
negative numbers are. Then scan second time and put every number is its
correct final position. This should be O(N) and O(1)
【在 c****p 的大作中提到】
: 一个未排序整数数组，有正负数，重新排列使负数排在正数前面，并且要求不改变原来
: 的相对顺序
: 比如：
: input:
: 1,7,-5,9,-12,15
: ans: -5,-12,1,7,9,15
: 要求时间复杂度O(N),空间O(1)
g*y
16 楼
Think again, that's not O(1) space.
Unless you calculate the correct positions and store them in O(n) space, you
cannot achieve O(n) in time.
【在 g***o 的大作中提到】
: One method I can think of is scanning once to find how many positive and
: negative numbers are. Then scan second time and put every number is its
: correct final position. This should be O(N) and O(1)
Unless you calculate the correct positions and store them in O(n) space, you
cannot achieve O(n) in time.
【在 g***o 的大作中提到】
: One method I can think of is scanning once to find how many positive and
: negative numbers are. Then scan second time and put every number is its
: correct final position. This should be O(N) and O(1)
m*e
17 楼
say you have n negatives
neg = 0; //start slot for negative numbers
pos = n; //start slot for positive numbers
//start examining array[0-N]
i = 0
while(neg
else swap array[pos] and array[i], pos++
i++
Think again, that's not O(1) space.
Unless you calculate the correct positions and store them in O(n) space, you
cannot achieve O(n) in time.
【在 g**********y 的大作中提到】
: Think again, that's not O(1) space.
: Unless you calculate the correct positions and store them in O(n) space, you
: cannot achieve O(n) in time.
neg = 0; //start slot for negative numbers
pos = n; //start slot for positive numbers
//start examining array[0-N]
i = 0
while(neg
else swap array[pos] and array[i], pos++
i++
Think again, that's not O(1) space.
Unless you calculate the correct positions and store them in O(n) space, you
cannot achieve O(n) in time.
【在 g**********y 的大作中提到】
: Think again, that's not O(1) space.
: Unless you calculate the correct positions and store them in O(n) space, you
: cannot achieve O(n) in time.
g*k
18 楼
read again, it requires stable
【在 m******e 的大作中提到】
: say you have n negatives
: neg = 0; //start slot for negative numbers
: pos = n; //start slot for positive numbers
: //start examining array[0-N]
: i = 0
: while(neg
: else swap array[pos] and array[i], pos++
: i++
:
【在 m******e 的大作中提到】
: say you have n negatives
: neg = 0; //start slot for negative numbers
: pos = n; //start slot for positive numbers
: //start examining array[0-N]
: i = 0
: while(neg
: else swap array[pos] and array[i], pos++
: i++
:
m*e
19 楼
it is stable
【在 g*****k 的大作中提到】
: read again, it requires stable
【在 g*****k 的大作中提到】
: read again, it requires stable
g*k
20 楼
think again!
【在 m******e 的大作中提到】
: it is stable
【在 m******e 的大作中提到】
: it is stable
g*y
21 楼
1, -1, 2, -2, 3, -3, 4, -4
so -1 should go pos 0, swap, ok
-1, 1, 2, -2, 3, -3, 4, -4
-2 should go pos 1, where should 1 go? pos 4, which is 3 now, swap.
Then where does 3 go? you don't know, unless you calculate it.
【在 m******e 的大作中提到】
: say you have n negatives
: neg = 0; //start slot for negative numbers
: pos = n; //start slot for positive numbers
: //start examining array[0-N]
: i = 0
: while(neg
: else swap array[pos] and array[i], pos++
: i++
:
so -1 should go pos 0, swap, ok
-1, 1, 2, -2, 3, -3, 4, -4
-2 should go pos 1, where should 1 go? pos 4, which is 3 now, swap.
Then where does 3 go? you don't know, unless you calculate it.
【在 m******e 的大作中提到】
: say you have n negatives
: neg = 0; //start slot for negative numbers
: pos = n; //start slot for positive numbers
: //start examining array[0-N]
: i = 0
: while(neg
: else swap array[pos] and array[i], pos++
: i++
:
m*e
22 楼
ok, my bad, keep track of range [0, neg) and [numNeg, pos), and do not
rearrange those (since they are already in the correct place)
use [neg, numNeg) and [pos, N) as circular buffer for un-processed elements
#include
#include
#include
using namespace std;
void print(const vector& input) {
for(size_t i = 0; i < input.size(); ++i) {
cout << input[i] << " ";
}
cout << endl;
}
int numNegatives(const vector& input) {
int cnt = 0;
for(size_t i = 0; i < input.size(); ++i) {
if(input[i] < 0) ++cnt;
}
return cnt;
}
void shuffleNegPos(vector & input, size_t numNeg) {
size_t neg = 0;
size_t pos = numNeg;
size_t i = 0;
while(neg< numNeg && pos < input.size()) {
if((i >= neg && i < numNeg) || i >= pos ) {
if(input[i] < 0) {
int temp = input[neg];
input[neg] = input[i];
input[i] = temp;
++neg ;
} else {
int temp = input[pos];
input[pos] = input[i];
input[i] = temp;
++pos ;
}
}
//print(input);
++i;
}
}
int main(int argc, const char* argv[]) {
std::vector input;
for(int i=1; i < argc; ++i) {
int n;
if(sscanf(argv[i], "%d", &n) > 0) {
input.push_back(n);
}
}
shuffleNegPos(input, numNegatives(input));
print(input);
return 0;
}
【在 g*****k 的大作中提到】
: think again!
rearrange those (since they are already in the correct place)
use [neg, numNeg) and [pos, N) as circular buffer for un-processed elements
#include
#include
#include
using namespace std;
void print(const vector
for(size_t i = 0; i < input.size(); ++i) {
cout << input[i] << " ";
}
cout << endl;
}
int numNegatives(const vector
int cnt = 0;
for(size_t i = 0; i < input.size(); ++i) {
if(input[i] < 0) ++cnt;
}
return cnt;
}
void shuffleNegPos(vector
size_t neg = 0;
size_t pos = numNeg;
size_t i = 0;
while(neg< numNeg && pos < input.size()) {
if((i >= neg && i < numNeg) || i >= pos ) {
if(input[i] < 0) {
int temp = input[neg];
input[neg] = input[i];
input[i] = temp;
++neg ;
} else {
int temp = input[pos];
input[pos] = input[i];
input[i] = temp;
++pos ;
}
}
//print(input);
++i;
}
}
int main(int argc, const char* argv[]) {
std::vector
for(int i=1; i < argc; ++i) {
int n;
if(sscanf(argv[i], "%d", &n) > 0) {
input.push_back(n);
}
}
shuffleNegPos(input, numNegatives(input));
print(input);
return 0;
}
【在 g*****k 的大作中提到】
: think again!
m*t
23 楼
这题就是快速排序里的partition算法。
用0作为pivot来划分，小于0的放在前面。随便一本算法书上都有介绍。
用0作为pivot来划分，小于0的放在前面。随便一本算法书上都有介绍。
k*n
24 楼
partition is not stable.
【在 m****t 的大作中提到】
: 这题就是快速排序里的partition算法。
: 用0作为pivot来划分，小于0的放在前面。随便一本算法书上都有介绍。
【在 m****t 的大作中提到】
: 这题就是快速排序里的partition算法。
: 用0作为pivot来划分，小于0的放在前面。随便一本算法书上都有介绍。
P*l
25 楼
看题不细啊。。
【在 m****t 的大作中提到】
: 这题就是快速排序里的partition算法。
: 用0作为pivot来划分，小于0的放在前面。随便一本算法书上都有介绍。
【在 m****t 的大作中提到】
: 这题就是快速排序里的partition算法。
: 用0作为pivot来划分，小于0的放在前面。随便一本算法书上都有介绍。
m*t
26 楼
如果 有0的 话，就是荷兰旗算法。复杂度就是O（N）。不知道为什么说not stable?
【在 P**l 的大作中提到】
: 看题不细啊。。
m*t
27 楼
荷兰旗算法，复杂度在任何情况下都是O（N）, 完全stable.
所以本题复杂度就是O（N）
i=j=0, k=N-1;
while (j<=k) {
if (a[j]<0) {
exchange a[i] a[j]
i++;
j++;
}
else if (a[j] > 0) {
exchange a[j] a[k]
k--;
}
else {
j++;
}
}
所以本题复杂度就是O（N）
i=j=0, k=N-1;
while (j<=k) {
if (a[j]<0) {
exchange a[i] a[j]
i++;
j++;
}
else if (a[j] > 0) {
exchange a[j] a[k]
k--;
}
else {
j++;
}
}
P*l
28 楼
前后互换的时候，相同颜色的乱序了啊
【在 m****t 的大作中提到】
: 荷兰旗算法，复杂度在任何情况下都是O（N）, 完全stable.
: 所以本题复杂度就是O（N）
: i=j=0, k=N-1;
: while (j<=k) {
: if (a[j]<0) {
: exchange a[i] a[j]
: i++;
: j++;
: }
: else if (a[j] > 0) {
【在 m****t 的大作中提到】
: 荷兰旗算法，复杂度在任何情况下都是O（N）, 完全stable.
: 所以本题复杂度就是O（N）
: i=j=0, k=N-1;
: while (j<=k) {
: if (a[j]<0) {
: exchange a[i] a[j]
: i++;
: j++;
: }
: else if (a[j] > 0) {
m*t
29 楼
确实是我看题不细。多谢。
【在 P**l 的大作中提到】
: 前后互换的时候，相同颜色的乱序了啊
c*p
30 楼
一个未排序整数数组，有正负数，重新排列使负数排在正数前面，并且要求不改变原来
的相对顺序
比如：
input:
1,7,-5,9,-12,15
ans: -5,-12,1,7,9,15
要求时间复杂度O(N),空间O(1)
的相对顺序
比如：
input:
1,7,-5,9,-12,15
ans: -5,-12,1,7,9,15
要求时间复杂度O(N),空间O(1)
f*t
31 楼
只能想到一个类似于bubble sort的解法，时间复杂度是O(N^2)...
g*k
32 楼
只能想到O(nlgn)的stable 算法，O(n)的没啥思路
【在 c****p 的大作中提到】
: 一个未排序整数数组，有正负数，重新排列使负数排在正数前面，并且要求不改变原来
: 的相对顺序
: 比如：
: input:
: 1,7,-5,9,-12,15
: ans: -5,-12,1,7,9,15
: 要求时间复杂度O(N),空间O(1)
【在 c****p 的大作中提到】
: 一个未排序整数数组，有正负数，重新排列使负数排在正数前面，并且要求不改变原来
: 的相对顺序
: 比如：
: input:
: 1,7,-5,9,-12,15
: ans: -5,-12,1,7,9,15
: 要求时间复杂度O(N),空间O(1)
b*r
33 楼
扫两边？
void reorder(int input[]){
int length=sizeof(input)/sizeof(int);
int output[length];
int last_negative_index=-1;
int i=0;
for (i=0; i
{
last_negative_index++;
// move this number before all the positive numbers.
output[last_negative_index]=input[i];
}
}
// now we have last_negative_index
for (i=0; i
output[last_negative_index+1]=input[i];
last_negetive_index++;
}
}
}
【在 c****p 的大作中提到】
: 一个未排序整数数组，有正负数，重新排列使负数排在正数前面，并且要求不改变原来
: 的相对顺序
: 比如：
: input:
: 1,7,-5,9,-12,15
: ans: -5,-12,1,7,9,15
: 要求时间复杂度O(N),空间O(1)
void reorder(int input[]){
int length=sizeof(input)/sizeof(int);
int output[length];
int last_negative_index=-1;
int i=0;
for (i=0; i
{
last_negative_index++;
// move this number before all the positive numbers.
output[last_negative_index]=input[i];
}
}
// now we have last_negative_index
for (i=0; i
output[last_negative_index+1]=input[i];
last_negetive_index++;
}
}
}
【在 c****p 的大作中提到】
: 一个未排序整数数组，有正负数，重新排列使负数排在正数前面，并且要求不改变原来
: 的相对顺序
: 比如：
: input:
: 1,7,-5,9,-12,15
: ans: -5,-12,1,7,9,15
: 要求时间复杂度O(N),空间O(1)
g*k
34 楼
O(1) space.
【在 b***r 的大作中提到】
: 扫两边？
: void reorder(int input[]){
: int length=sizeof(input)/sizeof(int);
: int output[length];
:
: int last_negative_index=-1;
: int i=0;
: for (i=0; i
: {
【在 b***r 的大作中提到】
: 扫两边？
: void reorder(int input[]){
: int length=sizeof(input)/sizeof(int);
: int output[length];
:
: int last_negative_index=-1;
: int i=0;
: for (i=0; i
: {
i*e
35 楼
Already found a bug in your code.
--> int length=sizeof(input)/sizeof(int);
This will always set lenght as 1. Because input is an int* pointer that's
passed into the function, therefore sizeof(input) = sizeof(int*) = 4.
【在 b***r 的大作中提到】
: 扫两边？
: void reorder(int input[]){
: int length=sizeof(input)/sizeof(int);
: int output[length];
:
: int last_negative_index=-1;
: int i=0;
: for (i=0; i
: {
--> int length=sizeof(input)/sizeof(int);
This will always set lenght as 1. Because input is an int* pointer that's
passed into the function, therefore sizeof(input) = sizeof(int*) = 4.
【在 b***r 的大作中提到】
: 扫两边？
: void reorder(int input[]){
: int length=sizeof(input)/sizeof(int);
: int output[length];
:
: int last_negative_index=-1;
: int i=0;
: for (i=0; i
: {
r*n
36 楼
需要考虑数值是0的情况么？
另外，如果要求in-place replacement，可以做到时间O(n)，空间O(1)么？
【在 b***r 的大作中提到】
: 扫两边？
: void reorder(int input[]){
: int length=sizeof(input)/sizeof(int);
: int output[length];
:
: int last_negative_index=-1;
: int i=0;
: for (i=0; i
: {
另外，如果要求in-place replacement，可以做到时间O(n)，空间O(1)么？
【在 b***r 的大作中提到】
: 扫两边？
: void reorder(int input[]){
: int length=sizeof(input)/sizeof(int);
: int output[length];
:
: int last_negative_index=-1;
: int i=0;
: for (i=0; i
: {
i*e
37 楼
From the discussions on SO, it seems unlikely there exist a solution with O(
N) time and O(1) space (or maybe it's a research problem). Dutch national
flag sorting can solve this in O(N) time and O(1) space, but is not stable.
http://stackoverflow.com/questions/5347616/how-to-sort-an-integ
N) time and O(1) space (or maybe it's a research problem). Dutch national
flag sorting can solve this in O(N) time and O(1) space, but is not stable.
http://stackoverflow.com/questions/5347616/how-to-sort-an-integ
b*r
38 楼
牛人啊。ｂｏｗ
【在 i**********e 的大作中提到】
: Already found a bug in your code.
: --> int length=sizeof(input)/sizeof(int);
: This will always set lenght as 1. Because input is an int* pointer that's
: passed into the function, therefore sizeof(input) = sizeof(int*) = 4.
【在 i**********e 的大作中提到】
: Already found a bug in your code.
: --> int length=sizeof(input)/sizeof(int);
: This will always set lenght as 1. Because input is an int* pointer that's
: passed into the function, therefore sizeof(input) = sizeof(int*) = 4.
b*g
39 楼
从后往前扫瞄到遇到第一个负数，
把这个负数与它前面的正数交换，直到，它前面也是负数
这样负数慢慢成堆，继续与之前的正数序列交换，直到数组的第一个元素。
比如：
3,4,1,7,-5,9,-12,15
-->
3,4,1,7,-5,-12,9,15
-->
-5，-12，1,7, 3，4，9,15
-->
-5,-12,3，4，1，7,9,15
负数序列和正数序列的交换比较tricky，但是应该是可以保证O(N)的，
以 3,4,1,7,-5,-12 为例
先把-5，-12同正数序列的头两个交换
得到
-5,-12,1,7,3,4,
然后，把，1,7,同3，4交换保证位置：
得到
-5,-12,3,4,1,7,
以此类推。
把m 连续的负数序列 同 之前的 k连续正数序列交换，可以在 m+k时间内完成，
【在 c****p 的大作中提到】
: 一个未排序整数数组，有正负数，重新排列使负数排在正数前面，并且要求不改变原来
: 的相对顺序
: 比如：
: input:
: 1,7,-5,9,-12,15
: ans: -5,-12,1,7,9,15
: 要求时间复杂度O(N),空间O(1)
把这个负数与它前面的正数交换，直到，它前面也是负数
这样负数慢慢成堆，继续与之前的正数序列交换，直到数组的第一个元素。
比如：
3,4,1,7,-5,9,-12,15
-->
3,4,1,7,-5,-12,9,15
-->
-5，-12，1,7, 3，4，9,15
-->
-5,-12,3，4，1，7,9,15
负数序列和正数序列的交换比较tricky，但是应该是可以保证O(N)的，
以 3,4,1,7,-5,-12 为例
先把-5，-12同正数序列的头两个交换
得到
-5,-12,1,7,3,4,
然后，把，1,7,同3，4交换保证位置：
得到
-5,-12,3,4,1,7,
以此类推。
把m 连续的负数序列 同 之前的 k连续正数序列交换，可以在 m+k时间内完成，
【在 c****p 的大作中提到】
: 一个未排序整数数组，有正负数，重新排列使负数排在正数前面，并且要求不改变原来
: 的相对顺序
: 比如：
: input:
: 1,7,-5,9,-12,15
: ans: -5,-12,1,7,9,15
: 要求时间复杂度O(N),空间O(1)
f*4
40 楼
给你个反例
1 -1 2 -2 3 -3 4 -4 5 -5 6 -6
你算一下要交换多少次吧
【在 b**********g 的大作中提到】
: 从后往前扫瞄到遇到第一个负数，
: 把这个负数与它前面的正数交换，直到，它前面也是负数
: 这样负数慢慢成堆，继续与之前的正数序列交换，直到数组的第一个元素。
: 比如：
: 3,4,1,7,-5,9,-12,15
: -->
: 3,4,1,7,-5,-12,9,15
: -->
: -5，-12，1,7, 3，4，9,15
: -->
1 -1 2 -2 3 -3 4 -4 5 -5 6 -6
你算一下要交换多少次吧
【在 b**********g 的大作中提到】
: 从后往前扫瞄到遇到第一个负数，
: 把这个负数与它前面的正数交换，直到，它前面也是负数
: 这样负数慢慢成堆，继续与之前的正数序列交换，直到数组的第一个元素。
: 比如：
: 3,4,1,7,-5,9,-12,15
: -->
: 3,4,1,7,-5,-12,9,15
: -->
: -5，-12，1,7, 3，4，9,15
: -->
p*z
41 楼
我有一个思路，但是没编程！大家讨论一下！
Hint：不知道大家有没有看过reverse the words in a sentence的例子,我简单说一下
I love you => you love I
程序：
1）reverse 每一个单词：I evol uoy
2) reverse 每整个句子： you love I
根据上面的例子，我们可以同理做这个题（我们先简化为只有前负后正）：5，7，9，-
1，-4 （不知道有大家有木有灵感，其实我们可以把上题的空格和这题的正负交界同比）
1） reverse 正和负的sub array： 9，7，5，-4，-1
2） reverse 这两个sub arrays：-1，-4，5，7，9
所以，把上面的例子复杂化： -1，-4，5，7，9，-1231，-123，54，3462
1）reverse 前面两个正和负的sub arrays：-1，-4，9，7，5，-123，-1231，54，
3462
2）reverse 这两个sub arrays：-1，-4，-1231，-123，5，7，9，，54，3462
所以总的来说：找到两个sub arrays 且前面的sub array都是正数，后面的sub array
都是负数就用这种方法来in place地换位置。请高手测评一下！
Hint：不知道大家有没有看过reverse the words in a sentence的例子,我简单说一下
I love you => you love I
程序：
1）reverse 每一个单词：I evol uoy
2) reverse 每整个句子： you love I
根据上面的例子，我们可以同理做这个题（我们先简化为只有前负后正）：5，7，9，-
1，-4 （不知道有大家有木有灵感，其实我们可以把上题的空格和这题的正负交界同比）
1） reverse 正和负的sub array： 9，7，5，-4，-1
2） reverse 这两个sub arrays：-1，-4，5，7，9
所以，把上面的例子复杂化： -1，-4，5，7，9，-1231，-123，54，3462
1）reverse 前面两个正和负的sub arrays：-1，-4，9，7，5，-123，-1231，54，
3462
2）reverse 这两个sub arrays：-1，-4，-1231，-123，5，7，9，，54，3462
所以总的来说：找到两个sub arrays 且前面的sub array都是正数，后面的sub array
都是负数就用这种方法来in place地换位置。请高手测评一下！
c*p
42 楼
这个可行，我在贴题的时候也想到了,但是应该不是O(N)
给定这样一个数列：
1 -1 2 -2 3 -3 4 -4 ... N/2 -N/2
这个已经是O(N^2)了。
，-
比）
【在 p****z 的大作中提到】
: 我有一个思路，但是没编程！大家讨论一下！
: Hint：不知道大家有没有看过reverse the words in a sentence的例子,我简单说一下
: I love you => you love I
: 程序：
: 1）reverse 每一个单词：I evol uoy
: 2) reverse 每整个句子： you love I
: 根据上面的例子，我们可以同理做这个题（我们先简化为只有前负后正）：5，7，9，-
: 1，-4 （不知道有大家有木有灵感，其实我们可以把上题的空格和这题的正负交界同比）
: 1） reverse 正和负的sub array： 9，7，5，-4，-1
: 2） reverse 这两个sub arrays：-1，-4，5，7，9
给定这样一个数列：
1 -1 2 -2 3 -3 4 -4 ... N/2 -N/2
这个已经是O(N^2)了。
，-
比）
【在 p****z 的大作中提到】
: 我有一个思路，但是没编程！大家讨论一下！
: Hint：不知道大家有没有看过reverse the words in a sentence的例子,我简单说一下
: I love you => you love I
: 程序：
: 1）reverse 每一个单词：I evol uoy
: 2) reverse 每整个句子： you love I
: 根据上面的例子，我们可以同理做这个题（我们先简化为只有前负后正）：5，7，9，-
: 1，-4 （不知道有大家有木有灵感，其实我们可以把上题的空格和这题的正负交界同比）
: 1） reverse 正和负的sub array： 9，7，5，-4，-1
: 2） reverse 这两个sub arrays：-1，-4，5，7，9
b*8
43 楼
就目前看到的很多例子，N时间1空间还要Inpace+Stable，一般很难同时满足，多数都
是少任何一个要求都行。
是少任何一个要求都行。
g*o
44 楼
One method I can think of is scanning once to find how many positive and
negative numbers are. Then scan second time and put every number is its
correct final position. This should be O(N) and O(1)
【在 c****p 的大作中提到】
: 一个未排序整数数组，有正负数，重新排列使负数排在正数前面，并且要求不改变原来
: 的相对顺序
: 比如：
: input:
: 1,7,-5,9,-12,15
: ans: -5,-12,1,7,9,15
: 要求时间复杂度O(N),空间O(1)
negative numbers are. Then scan second time and put every number is its
correct final position. This should be O(N) and O(1)
【在 c****p 的大作中提到】
: 一个未排序整数数组，有正负数，重新排列使负数排在正数前面，并且要求不改变原来
: 的相对顺序
: 比如：
: input:
: 1,7,-5,9,-12,15
: ans: -5,-12,1,7,9,15
: 要求时间复杂度O(N),空间O(1)
g*y
45 楼
Think again, that's not O(1) space.
Unless you calculate the correct positions and store them in O(n) space, you
cannot achieve O(n) in time.
【在 g***o 的大作中提到】
: One method I can think of is scanning once to find how many positive and
: negative numbers are. Then scan second time and put every number is its
: correct final position. This should be O(N) and O(1)
Unless you calculate the correct positions and store them in O(n) space, you
cannot achieve O(n) in time.
【在 g***o 的大作中提到】
: One method I can think of is scanning once to find how many positive and
: negative numbers are. Then scan second time and put every number is its
: correct final position. This should be O(N) and O(1)
m*e
46 楼
say you have n negatives
neg = 0; //start slot for negative numbers
pos = n; //start slot for positive numbers
//start examining array[0-N]
i = 0
while(neg
else swap array[pos] and array[i], pos++
i++
Think again, that's not O(1) space.
Unless you calculate the correct positions and store them in O(n) space, you
cannot achieve O(n) in time.
【在 g**********y 的大作中提到】
: Think again, that's not O(1) space.
: Unless you calculate the correct positions and store them in O(n) space, you
: cannot achieve O(n) in time.
neg = 0; //start slot for negative numbers
pos = n; //start slot for positive numbers
//start examining array[0-N]
i = 0
while(neg
else swap array[pos] and array[i], pos++
i++
Think again, that's not O(1) space.
Unless you calculate the correct positions and store them in O(n) space, you
cannot achieve O(n) in time.
【在 g**********y 的大作中提到】
: Think again, that's not O(1) space.
: Unless you calculate the correct positions and store them in O(n) space, you
: cannot achieve O(n) in time.
g*k
47 楼
read again, it requires stable
【在 m******e 的大作中提到】
: say you have n negatives
: neg = 0; //start slot for negative numbers
: pos = n; //start slot for positive numbers
: //start examining array[0-N]
: i = 0
: while(neg
: else swap array[pos] and array[i], pos++
: i++
:
【在 m******e 的大作中提到】
: say you have n negatives
: neg = 0; //start slot for negative numbers
: pos = n; //start slot for positive numbers
: //start examining array[0-N]
: i = 0
: while(neg
: else swap array[pos] and array[i], pos++
: i++
:
m*e
48 楼
it is stable
【在 g*****k 的大作中提到】
: read again, it requires stable
【在 g*****k 的大作中提到】
: read again, it requires stable
g*k
49 楼
think again!
【在 m******e 的大作中提到】
: it is stable
【在 m******e 的大作中提到】
: it is stable
g*y
50 楼
1, -1, 2, -2, 3, -3, 4, -4
so -1 should go pos 0, swap, ok
-1, 1, 2, -2, 3, -3, 4, -4
-2 should go pos 1, where should 1 go? pos 4, which is 3 now, swap.
Then where does 3 go? you don't know, unless you calculate it.
【在 m******e 的大作中提到】
: say you have n negatives
: neg = 0; //start slot for negative numbers
: pos = n; //start slot for positive numbers
: //start examining array[0-N]
: i = 0
: while(neg
: else swap array[pos] and array[i], pos++
: i++
:
so -1 should go pos 0, swap, ok
-1, 1, 2, -2, 3, -3, 4, -4
-2 should go pos 1, where should 1 go? pos 4, which is 3 now, swap.
Then where does 3 go? you don't know, unless you calculate it.
【在 m******e 的大作中提到】
: say you have n negatives
: neg = 0; //start slot for negative numbers
: pos = n; //start slot for positive numbers
: //start examining array[0-N]
: i = 0
: while(neg
: else swap array[pos] and array[i], pos++
: i++
:
m*t
51 楼
这题就是快速排序里的partition算法。
用0作为pivot来划分，小于0的放在前面。随便一本算法书上都有介绍。
用0作为pivot来划分，小于0的放在前面。随便一本算法书上都有介绍。
k*n
52 楼
partition is not stable.
【在 m****t 的大作中提到】
: 这题就是快速排序里的partition算法。
: 用0作为pivot来划分，小于0的放在前面。随便一本算法书上都有介绍。
【在 m****t 的大作中提到】
: 这题就是快速排序里的partition算法。
: 用0作为pivot来划分，小于0的放在前面。随便一本算法书上都有介绍。
P*l
53 楼
看题不细啊。。
【在 m****t 的大作中提到】
: 这题就是快速排序里的partition算法。
: 用0作为pivot来划分，小于0的放在前面。随便一本算法书上都有介绍。
【在 m****t 的大作中提到】
: 这题就是快速排序里的partition算法。
: 用0作为pivot来划分，小于0的放在前面。随便一本算法书上都有介绍。
m*t
54 楼
如果 有0的 话，就是荷兰旗算法。复杂度就是O（N）。不知道为什么说not stable?
【在 P**l 的大作中提到】
: 看题不细啊。。
m*t
55 楼
荷兰旗算法，复杂度在任何情况下都是O（N）, 完全stable.
所以本题复杂度就是O（N）
i=j=0, k=N-1;
while (j<=k) {
if (a[j]<0) {
exchange a[i] a[j]
i++;
j++;
}
else if (a[j] > 0) {
exchange a[j] a[k]
k--;
}
else {
j++;
}
}
所以本题复杂度就是O（N）
i=j=0, k=N-1;
while (j<=k) {
if (a[j]<0) {
exchange a[i] a[j]
i++;
j++;
}
else if (a[j] > 0) {
exchange a[j] a[k]
k--;
}
else {
j++;
}
}
P*l
56 楼
前后互换的时候，相同颜色的乱序了啊
【在 m****t 的大作中提到】
: 荷兰旗算法，复杂度在任何情况下都是O（N）, 完全stable.
: 所以本题复杂度就是O（N）
: i=j=0, k=N-1;
: while (j<=k) {
: if (a[j]<0) {
: exchange a[i] a[j]
: i++;
: j++;
: }
: else if (a[j] > 0) {
【在 m****t 的大作中提到】
: 荷兰旗算法，复杂度在任何情况下都是O（N）, 完全stable.
: 所以本题复杂度就是O（N）
: i=j=0, k=N-1;
: while (j<=k) {
: if (a[j]<0) {
: exchange a[i] a[j]
: i++;
: j++;
: }
: else if (a[j] > 0) {
m*t
57 楼
确实是我看题不细。多谢。
【在 P**l 的大作中提到】
: 前后互换的时候，相同颜色的乱序了啊
y*r
58 楼
把quicksort的partition算法变形一下就可以了
【在 c****p 的大作中提到】
: 一个未排序整数数组，有正负数，重新排列使负数排在正数前面，并且要求不改变原来
: 的相对顺序
: 比如：
: input:
: 1,7,-5,9,-12,15
: ans: -5,-12,1,7,9,15
: 要求时间复杂度O(N),空间O(1)
【在 c****p 的大作中提到】
: 一个未排序整数数组，有正负数，重新排列使负数排在正数前面，并且要求不改变原来
: 的相对顺序
: 比如：
: input:
: 1,7,-5,9,-12,15
: ans: -5,-12,1,7,9,15
: 要求时间复杂度O(N),空间O(1)
l*c
59 楼
should be no solution, otherwise, quicksort become stable, big improvement
【在 y*********r 的大作中提到】
: 把quicksort的partition算法变形一下就可以了
【在 y*********r 的大作中提到】
: 把quicksort的partition算法变形一下就可以了
l*c
60 楼
if the sequence is
1, -5, 7, 9, -12, 15..
your algorithm does not work
Basically, it is impossible to keep stable with partition O(n)
1, -5, 7, 9, -12, 15..
your algorithm does not work
Basically, it is impossible to keep stable with partition O(n)
r*h
61 楼
代码有小问题，但是思路是正确的
【在 m****t 的大作中提到】
: 荷兰旗算法，复杂度在任何情况下都是O（N）, 完全stable.
: 所以本题复杂度就是O（N）
: i=j=0, k=N-1;
: while (j<=k) {
: if (a[j]<0) {
: exchange a[i] a[j]
: i++;
: j++;
: }
: else if (a[j] > 0) {
【在 m****t 的大作中提到】
: 荷兰旗算法，复杂度在任何情况下都是O（N）, 完全stable.
: 所以本题复杂度就是O（N）
: i=j=0, k=N-1;
: while (j<=k) {
: if (a[j]<0) {
: exchange a[i] a[j]
: i++;
: j++;
: }
: else if (a[j] > 0) {
l*c
62 楼
not stable
【在 r*******h 的大作中提到】
: 代码有小问题，但是思路是正确的
【在 r*******h 的大作中提到】
: 代码有小问题，但是思路是正确的
l*c
63 楼
this kind of swap operation is not stable algorithm
【在 m****t 的大作中提到】
: 荷兰旗算法，复杂度在任何情况下都是O（N）, 完全stable.
: 所以本题复杂度就是O（N）
: i=j=0, k=N-1;
: while (j<=k) {
: if (a[j]<0) {
: exchange a[i] a[j]
: i++;
: j++;
: }
: else if (a[j] > 0) {
【在 m****t 的大作中提到】
: 荷兰旗算法，复杂度在任何情况下都是O（N）, 完全stable.
: 所以本题复杂度就是O（N）
: i=j=0, k=N-1;
: while (j<=k) {
: if (a[j]<0) {
: exchange a[i] a[j]
: i++;
: j++;
: }
: else if (a[j] > 0) {
r*h
64 楼
你试一下就知道了，这个算法的本质就是stable的，和两头扫描对换的方法不一样。
【在 l******c 的大作中提到】
: not stable
【在 l******c 的大作中提到】
: not stable
l*c
65 楼
for this simple case, what's procedure?
how to do stable swap for O(n)?
1, -2, -3, 4, 5, 6,-7
【在 r*******h 的大作中提到】
: 你试一下就知道了，这个算法的本质就是stable的，和两头扫描对换的方法不一样。
how to do stable swap for O(n)?
1, -2, -3, 4, 5, 6,-7
【在 r*******h 的大作中提到】
: 你试一下就知道了，这个算法的本质就是stable的，和两头扫描对换的方法不一样。
a*6
66 楼
所谓的quicksort不stable不是说partition那一步，而是选pivot那步
一般认为的quicksort，（递归的）每次随机选一个pivot，然后partition，复杂度期
望下是O(nlogn)，最坏是O(n^2)，这个可能是你说的不stable
但是partition那一步肯定是O(n)的
理想情况下，如果pivot选到median，那么复杂度肯定是O(nlogn)了
有一种确定性算法可以每次以O(n)的时间选到一个pivot在median附近（至少1/3的元素
小于他，同时至少1/3的元素大于他），那么这样quicksort的复杂度最坏情况下也是O(
nlogn)了，不过实际中没太多人用这个版本，因为其实实际的performance不如那个随
机选pivot的版本
【在 l******c 的大作中提到】
: this kind of swap operation is not stable algorithm
一般认为的quicksort，（递归的）每次随机选一个pivot，然后partition，复杂度期
望下是O(nlogn)，最坏是O(n^2)，这个可能是你说的不stable
但是partition那一步肯定是O(n)的
理想情况下，如果pivot选到median，那么复杂度肯定是O(nlogn)了
有一种确定性算法可以每次以O(n)的时间选到一个pivot在median附近（至少1/3的元素
小于他，同时至少1/3的元素大于他），那么这样quicksort的复杂度最坏情况下也是O(
nlogn)了，不过实际中没太多人用这个版本，因为其实实际的performance不如那个随
机选pivot的版本
【在 l******c 的大作中提到】
: this kind of swap operation is not stable algorithm
k*n
67 楼
你都没搞明白sort里面的Stable是指什么。。。
O(
【在 a*******6 的大作中提到】
: 所谓的quicksort不stable不是说partition那一步，而是选pivot那步
: 一般认为的quicksort，（递归的）每次随机选一个pivot，然后partition，复杂度期
: 望下是O(nlogn)，最坏是O(n^2)，这个可能是你说的不stable
: 但是partition那一步肯定是O(n)的
: 理想情况下，如果pivot选到median，那么复杂度肯定是O(nlogn)了
: 有一种确定性算法可以每次以O(n)的时间选到一个pivot在median附近（至少1/3的元素
: 小于他，同时至少1/3的元素大于他），那么这样quicksort的复杂度最坏情况下也是O(
: nlogn)了，不过实际中没太多人用这个版本，因为其实实际的performance不如那个随
: 机选pivot的版本
O(
【在 a*******6 的大作中提到】
: 所谓的quicksort不stable不是说partition那一步，而是选pivot那步
: 一般认为的quicksort，（递归的）每次随机选一个pivot，然后partition，复杂度期
: 望下是O(nlogn)，最坏是O(n^2)，这个可能是你说的不stable
: 但是partition那一步肯定是O(n)的
: 理想情况下，如果pivot选到median，那么复杂度肯定是O(nlogn)了
: 有一种确定性算法可以每次以O(n)的时间选到一个pivot在median附近（至少1/3的元素
: 小于他，同时至少1/3的元素大于他），那么这样quicksort的复杂度最坏情况下也是O(
: nlogn)了，不过实际中没太多人用这个版本，因为其实实际的performance不如那个随
: 机选pivot的版本
a*6
68 楼
。。。确实把这里的stable搞错了，难怪lc说有swap就不stable，这是对的
【在 k****n 的大作中提到】
: 你都没搞明白sort里面的Stable是指什么。。。
:
: O(
【在 k****n 的大作中提到】
: 你都没搞明白sort里面的Stable是指什么。。。
:
: O(
r*h
69 楼
-7,-2,-3,4,5,6,1
-2,-7,-3,4,5,6,1
-2,-3,-7,4,5,6,1
-2,-3,-7,1,5,6,4
-2,-3,-7,1,4,6,5
-2,-3,-7,1,4,5,6
【在 l******c 的大作中提到】
: for this simple case, what's procedure?
: how to do stable swap for O(n)?
: 1, -2, -3, 4, 5, 6,-7
-2,-7,-3,4,5,6,1
-2,-3,-7,4,5,6,1
-2,-3,-7,1,5,6,4
-2,-3,-7,1,4,6,5
-2,-3,-7,1,4,5,6
【在 l******c 的大作中提到】
: for this simple case, what's procedure?
: how to do stable swap for O(n)?
: 1, -2, -3, 4, 5, 6,-7
l*c
70 楼
then it is not O(n)
after the swap(1, -1), you need move every element
a typical O(n**2) algorithm
【在 r*******h 的大作中提到】
: -7,-2,-3,4,5,6,1
: -2,-7,-3,4,5,6,1
: -2,-3,-7,4,5,6,1
: -2,-3,-7,1,5,6,4
: -2,-3,-7,1,4,6,5
: -2,-3,-7,1,4,5,6
after the swap(1, -1), you need move every element
a typical O(n**2) algorithm
【在 r*******h 的大作中提到】
: -7,-2,-3,4,5,6,1
: -2,-7,-3,4,5,6,1
: -2,-3,-7,4,5,6,1
: -2,-3,-7,1,5,6,4
: -2,-3,-7,1,4,6,5
: -2,-3,-7,1,4,5,6
l*c
71 楼
then it is not O(n)
after the swap(1, -7), you need move every element
a typical O(n**2) algorithm
【在 r*******h 的大作中提到】
: -7,-2,-3,4,5,6,1
: -2,-7,-3,4,5,6,1
: -2,-3,-7,4,5,6,1
: -2,-3,-7,1,5,6,4
: -2,-3,-7,1,4,6,5
: -2,-3,-7,1,4,5,6
after the swap(1, -7), you need move every element
a typical O(n**2) algorithm
【在 r*******h 的大作中提到】
: -7,-2,-3,4,5,6,1
: -2,-7,-3,4,5,6,1
: -2,-3,-7,4,5,6,1
: -2,-3,-7,1,5,6,4
: -2,-3,-7,1,4,6,5
: -2,-3,-7,1,4,5,6
h*n
72 楼
O(n)时间, O(1)空间，保持顺序，
这三个只能保证其中两个，应该不存在同时满足这三个的算法，链表倒是可以做到
任何涉及到交换的算法都保证不了顺序
任何涉及到冒泡的方法都保证不了时间
这三个只能保证其中两个，应该不存在同时满足这三个的算法，链表倒是可以做到
任何涉及到交换的算法都保证不了顺序
任何涉及到冒泡的方法都保证不了时间
s*e
73 楼
我想到一个笨方法，只适用于小的整数，即max * min 不能溢出。
不swap,硬把正的数插入该插入的地方。比如 从左边扫描，skip负的，遇到第一个正数
A[i]，这个正数a[i]要放在的位置是N （N =所有负数个数，下一个正数放在N+１）。
如果 A［N］＞０，A［N］ = A［N］ + (Max+1)*a[i], 如果a[N] <0, A[N] = A[N] +
(Min-1)*A[i].
以后遇到a[j]，如果 a[j]＞max or a[j] < min, 就解码
a[j] = a[j] % Max (or Min if a[j] <0), injected 正数是a[j] / Max (or Min if
a[j] <0).
解码后的负数直接overwrite它应该在的位置，解码后的正数重复第一个整数的操作，
最后a[j] = injected 正数.
不swap,硬把正的数插入该插入的地方。比如 从左边扫描，skip负的，遇到第一个正数
A[i]，这个正数a[i]要放在的位置是N （N =所有负数个数，下一个正数放在N+１）。
如果 A［N］＞０，A［N］ = A［N］ + (Max+1)*a[i], 如果a[N] <0, A[N] = A[N] +
(Min-1)*A[i].
以后遇到a[j]，如果 a[j]＞max or a[j] < min, 就解码
a[j] = a[j] % Max (or Min if a[j] <0), injected 正数是a[j] / Max (or Min if
a[j] <0).
解码后的负数直接overwrite它应该在的位置，解码后的正数重复第一个整数的操作，
最后a[j] = injected 正数.
相关阅读
好好练英文吧HR问薪资要求，如何回答请教：国内多年工作经验，无美国学位，可不可能找到一个non-profit H1B职位？FY2012 H1B申请在４月份的时候是多少份？没救了，自己做过的题几天后就忘了请问非码工的找工作讨论在哪里发文啊现在还有机会找暑期实习吗 伤心啊求 fb facebook 的refer, 谢谢为什么查不到OPT的状态呢网上最新最全的E-Verify Database发7道变态码工题，大家帮忙解解，3包子一题Google 如果股票split 2 for 1是不是GSU就直接贬值一半？上楼梯问题的时间复杂度是o(n)还是 nlogn?急急急，大家帮忙看一下。给包子!为什么amazon这么一个大公司盈利却很少？CPT期间是不是只能给CPT上的雇主工作？求近期成功拿到EAD的case休士顿工作机会-Controller (转载)怎么才算正式录用完事？Arista Networks 在狂招网络软工