四岁的男孩和爸妈一起特别害羞，可是如果爸妈不在身边特别social,这是什么原因啊 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Parenting - 为人父母

四岁的男孩和爸妈一起特别害羞，可是如果爸妈不在身边特别social,这是什么原因啊

四岁的男孩和爸妈一起特别害羞，可是如果爸妈不在身边特别social,这是什么原因啊# Parenting - 为人父母

x*o2014-03-15 07:03

1 楼

结婚半年，跟着ld过来三个月了，是J2。现在只上了ESL，其余的时间呆家里的多。虽
然不讨厌做饭，收拾家务，但也总想利用这里的机会提升一下自己，将来回国了找工作
什么的也容易些。
1.读书。如果我不想和ld两地的话，我该申请什么学校呢？还是在就近的学校辅修一些
专业？
2.工作。没有美国本土文凭，肯定不好找吧？再者，我们的地方很偏，根本没有太多的
单位。
3.安心做housewife,然后计划要娃。
想问问跟我经历相似的人，你们是怎么过来的？

u*l2014-03-15 07:03

2 楼

一个Array，比如A[]=[5,6,8,2,3,9,4]
输出要求是所有的奇数在偶数的前面，并保留相对顺序。
output: [5,3,9,6,8,2,4].
老印面试官：要求：
In-place (no additional place);
时间复杂度： O(N).

n*e2014-03-15 07:03

3 楼

是我们自己教育方法有问题吗？为什么孩子有父母在旁边很放不开呢。。。

V*82014-03-15 07:03

4 楼

I would choose #1.
Financial independence is the key, going back to school gets you on the
right track.

w*x2014-03-15 07:03

5 楼

//Given an array of positive and negative integers,
//re-arrange it so that you have postives on one end
//and negatives on the other, BUT retain the original order of appearance.
do it in-place
//e.g. 1, 7, -5, 9, -12, 15 => -5, -12, 1, 7, 9, 15
//When considering optimization from O(n^2) to O(nlogn),use divided &
conquer
void swapRange(int a[], int nBeg, int nEnd)
{
assert(a && nBeg <= nEnd);
while (nBeg < nEnd)
swap(a[nBeg++], a[nEnd--]);
}
//solution:
//e.g. in any stage: ---- "+++ --" ++++, reverse middle part
// ==> ---- "--" "+++" ++++, reverse middle 2 parts seperatly to keep "
stable"
void ReArrange(int a[], int n)
{
assert(a && n > 0);
if (n <= 1) return;
ReArrange(a, n/2);
ReArrange(a + n/2, n - n/2); //pitfall, notice both parameters
int nLft = 0;
while (a[nLft] < 0)
nLft++;
int nRgt = n-1;
while (a[nRgt] >= 0)
nRgt--;

//Very important, no need to swap under this situation, return
if (nRgt <= nLft) return;
swapRange(a, nLft, nRgt);
int nBegRgt = nLft;
while (a[nBegRgt] < 0) //no need to use "&& nBegRgt < n"
nBegRgt++;
swapRange(a, nLft, nBegRgt-1);
swapRange(a, nBegRgt, nRgt);
}

x*o2014-03-15 07:03

6 楼

很喜欢你的头像，超可爱；）
如果申请读研的话，那很可能得两地吧？要真这样了，那感觉就是走了另一条路了。

【在 V*****8 的大作中提到】

: I would choose #1.
: Financial independence is the key, going back to school gets you on the
: right track.

u*l2014-03-15 07:03

7 楼

你的这个计算复杂度是多少？
O(N) or O(Lgn)?

【在 w****x 的大作中提到】

: //Given an array of positive and negative integers,
: //re-arrange it so that you have postives on one end
: //and negatives on the other, BUT retain the original order of appearance.
: do it in-place
: //e.g. 1, 7, -5, 9, -12, 15 => -5, -12, 1, 7, 9, 15
: //When considering optimization from O(n^2) to O(nlogn),use divided &
: conquer
: void swapRange(int a[], int nBeg, int nEnd)
: {
: assert(a && nBeg <= nEnd);

k*e2014-03-15 07:03

8 楼

如果30了，就要孩子。不过还不到30，就读书或者工作
如果本科学历以下，就读书
如果国内有工作经验，英语尚好，就找工作试试看

【在 x******o 的大作中提到】

: 结婚半年，跟着ld过来三个月了，是J2。现在只上了ESL，其余的时间呆家里的多。虽
: 然不讨厌做饭，收拾家务，但也总想利用这里的机会提升一下自己，将来回国了找工作
: 什么的也容易些。
: 1.读书。如果我不想和ld两地的话，我该申请什么学校呢？还是在就近的学校辅修一些
: 专业？
: 2.工作。没有美国本土文凭，肯定不好找吧？再者，我们的地方很偏，根本没有太多的
: 单位。
: 3.安心做housewife,然后计划要娃。
: 想问问跟我经历相似的人，你们是怎么过来的？

w*x2014-03-15 07:03

9 楼

nlogn 吧

【在 u*l 的大作中提到】

: 你的这个计算复杂度是多少？
: O(N) or O(Lgn)?

V*82014-03-15 07:03

10 楼

Thank you, it's my son =)
no local school in your area? well... if that's the case, I'd rather choose
to be long distance. Eventually It's gonna be a dead end if you stay with
your husband but without the ability to find a job. Maybe you can have kids,
but that would make you 100% dependent, and probably burden to him.

【在 x******o 的大作中提到】

: 很喜欢你的头像，超可爱；）
: 如果申请读研的话，那很可能得两地吧？要真这样了，那感觉就是走了另一条路了。

u*l2014-03-15 07:03

11 楼

人家（老印）面试官要O（N)

【在 w****x 的大作中提到】

:
: nlogn 吧

x*o2014-03-15 07:03

12 楼

哇，没想到啊，我一看这么漂亮，以为是别处的图片什么的，mm好福气啊。

choose
kids,

【在 V*****8 的大作中提到】

: Thank you, it's my son =)
: no local school in your area? well... if that's the case, I'd rather choose
: to be long distance. Eventually It's gonna be a dead end if you stay with
: your husband but without the ability to find a job. Maybe you can have kids,
: but that would make you 100% dependent, and probably burden to him.

c*t2014-03-15 07:03

13 楼

O(n)
public int[] sortOddEven(int[] arr) {
if (arr == null || arr.length <= 1) return arr;
int i = 0, j = arr.length - 1;
while (i < j) {
while (i < j && arr[i] % 2 == 1) i++;
while (i < j && arr[j] % 2 == 0) j--;
if (i < j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
i++;
j--;
}
return arr;
}

【在 u*l 的大作中提到】

: 一个Array，比如A[]=[5,6,8,2,3,9,4]
: 输出要求是所有的奇数在偶数的前面，并保留相对顺序。
: output: [5,3,9,6,8,2,4].
: 老印面试官：要求：
: In-place (no additional place);
: 时间复杂度： O(N).

V*82014-03-15 07:03

14 楼

Thank you very much, please vote for him at the link below!

【在 x******o 的大作中提到】

: 哇，没想到啊，我一看这么漂亮，以为是别处的图片什么的，mm好福气啊。
:
: choose
: kids,

m*s2014-03-15 07:03

15 楼

印象里是道恶心题。。。跟啥杨表求中位数之流一个味道。。。
实际上就是stable_partition，如果去翻各种c++ stl的实现，会发现用的是O(nlogn)
的分治，也是现实中最好用的。。。不过如果要追求O(n)，那就要翻paper了orz。读懂
了在面试中也说不明白。。。
在这个问题里，虽然数组元素是有限整数，不过我是看不出来有啥用处。。。

【在 u*l 的大作中提到】

x*o2014-03-15 07:03

16 楼

俺已经投了嘿嘿。

【在 V*****8 的大作中提到】

: Thank you very much, please vote for him at the link below!

u*l2014-03-15 07:03

17 楼

顺序（Ordering)乱了吧？

【在 c********t 的大作中提到】

: O(n)
: public int[] sortOddEven(int[] arr) {
: if (arr == null || arr.length <= 1) return arr;
: int i = 0, j = arr.length - 1;
: while (i < j) {
: while (i < j && arr[i] % 2 == 1) i++;
: while (i < j && arr[j] % 2 == 0) j--;
: if (i < j) {
: int tmp = arr[i];
: arr[i] = arr[j];

b*r2014-03-15 07:03

18 楼

如果lg对你好的话，做家务生小孩也是很好的选择。

c*w2014-03-15 07:03

19 楼

你这个出来不是 [5,9,3,2,8,6,4] 吗？

l*c2014-03-15 07:03

20 楼

not the same sequence, no stable

【在 c********t 的大作中提到】

c*t2014-03-15 07:03

21 楼

嗯，又土了

【在 u*l 的大作中提到】

: 顺序（Ordering)乱了吧？

t*h2014-03-15 07:03

22 楼

这不就是典型的partition吗？

【在 u*l 的大作中提到】

c*t2014-03-15 07:03

23 楼

说实在，O(nlogn)我都想不出，阿三好狠的题。

【在 t*********h 的大作中提到】

: 这不就是典型的partition吗？

l*i2014-03-15 07:03

24 楼

被一个好人老印问过，写了个O(n^2)，之后说了O(nlogn)的思路，还表扬我算法好。这
个跟另一个题是一回事，
given a1,b1,a2,b2,a3,b3
transform into a1,a2,a3,b1,b2,b3

f*e2014-03-15 07:03

25 楼

这个题以前本版出现过，到底答案是什么？

【在 m******s 的大作中提到】

: 印象里是道恶心题。。。跟啥杨表求中位数之流一个味道。。。
: 实际上就是stable_partition，如果去翻各种c++ stl的实现，会发现用的是O(nlogn)
: 的分治，也是现实中最好用的。。。不过如果要追求O(n)，那就要翻paper了orz。读懂
: 了在面试中也说不明白。。。
: 在这个问题里，虽然数组元素是有限整数，不过我是看不出来有啥用处。。。

s*02014-03-15 07:03

26 楼

同问。

【在 f*****e 的大作中提到】

: 这个题以前本版出现过，到底答案是什么？

f*e2014-03-15 07:03

27 楼

如果数的范围很小，就用高几位表示index，低几位表示value？
还是变相利用了额外空间。

【在 s****0 的大作中提到】

: 同问。

w*p2014-03-15 07:03

28 楼

根据要求 In-place，那么只能是数字之间swap
时间复杂度： O(N).
这两点加起来只能是quick 里面的一步patition，就是array 分成两块一边放奇数，一
边放偶数
但是不stable.
观察下input array是有特点的。根据数据特点把它变成stable的。
1。可以数出来有几个奇数，偶数，这样array分成subArray的size出来了。m=size of
奇数
2。同时找到最大值
3。将所有的奇数加上最大值＊2
4。 two points point to end of each subArrays
5. swap (这里有点小小trick, 不然也会错）
6。把奇数恢复到原来的值－ 2＊Max
只是出来思路，code还没出来，纸上画了下，是work的。

【在 u*l 的大作中提到】

s*02014-03-15 07:03

29 楼

不对吧。
再试试。。。

【在 f*****e 的大作中提到】

: 如果数的范围很小，就用高几位表示index，低几位表示value？
: 还是变相利用了额外空间。

d*x2014-03-15 07:03

30 楼

of
~~~~~~~~~~~~~~~~~~~~~~~~~~~~........

【在 w********p 的大作中提到】

: 根据要求 In-place，那么只能是数字之间swap
: 时间复杂度： O(N).
: 这两点加起来只能是quick 里面的一步patition，就是array 分成两块一边放奇数，一
: 边放偶数
: 但是不stable.
: 观察下input array是有特点的。根据数据特点把它变成stable的。
: 1。可以数出来有几个奇数，偶数，这样array分成subArray的size出来了。m=size of
: 奇数
: 2。同时找到最大值
: 3。将所有的奇数加上最大值＊2

t*h2014-03-15 07:03

31 楼

刚想了一个很简单的发现部stable

【在 c********t 的大作中提到】

: 说实在，O(nlogn)我都想不出，阿三好狠的题。

f*e2014-03-15 07:03

32 楼

先都搞为正的，然后换成prefix sum，然后对prefix sum排序，再相减。

【在 t*********h 的大作中提到】

: 刚想了一个很简单的发现部stable

t*h2014-03-15 07:03

33 楼

one way is to first remember each position by remebering odd/even number's
index:
5 6 8 2 3 9 4
odd: 5[0] 3[1] 9[2]
even: 6[0] 8[1] 2[2] 4[3]
then partition sort:
5 6 8 2 3 9 4 ->
5 3 9 2 6 8 4 ->
5[0] 3[1] 9[2] 2[2] 6[0] 8[1] 4[3]
while(index[i]!=index[index[i]]) swap(i,index[i]);
finally we get:
5[0] 3[1] 9[2] 6[0] 8[1] 2[2] 4[3]
I believe this is O(n).

【在 t*********h 的大作中提到】

: 刚想了一个很简单的发现部stable

w*p2014-03-15 07:03

34 楼

写的时候发现用quick sort 的partition, 还是有问题。
用merge sort 的partition. 速度在O(n) （最快）和O(logn) （wrose) 之间

of

【在 w********p 的大作中提到】

c*t2014-03-15 07:03

35 楼

这道题除非是2^n的长度，否则我真写不出O(nlogn),你是什么思路？

【在 l***i 的大作中提到】

: 被一个好人老印问过，写了个O(n^2)，之后说了O(nlogn)的思路，还表扬我算法好。这
: 个跟另一个题是一回事，
: given a1,b1,a2,b2,a3,b3
: transform into a1,a2,a3,b1,b2,b3

h*n2014-03-15 07:03

36 楼

这个题我从来没见过stable，in place + O（n）的算法
怀疑根本就是不可能做到的事情，
这个题估计烙印就是专门要挂你吧，看似简单，其实不简单

【在 u*l 的大作中提到】

h*n2014-03-15 07:03

37 楼

你这已经不是inplace了，不能用额外空间

【在 t*********h 的大作中提到】

: one way is to first remember each position by remebering odd/even number's
: index:
: 5 6 8 2 3 9 4
: odd: 5[0] 3[1] 9[2]
: even: 6[0] 8[1] 2[2] 4[3]
: then partition sort:
: 5 6 8 2 3 9 4 ->
: 5 3 9 2 6 8 4 ->
: 5[0] 3[1] 9[2] 2[2] 6[0] 8[1] 4[3]
: while(index[i]!=index[index[i]]) swap(i,index[i]);

w*p2014-03-15 07:03

38 楼

remember each position space 是O(N) ?

【在 t*********h 的大作中提到】

t*h2014-03-15 07:03

39 楼

那没招了放弃烙印是来刷LZ的吧...

【在 h****n 的大作中提到】

: 你这已经不是inplace了，不能用额外空间

l*i2014-03-15 07:03

40 楼

divide and conquer, split at half, recurse, then swap mid part
a1, b1, a2, b2, a3, b3
a1, a2, b1 || a3, b2, b3
a1, a2, a3, b1, b2, b3

【在 c********t 的大作中提到】

: 这道题除非是2^n的长度，否则我真写不出O(nlogn),你是什么思路？

y*n2014-03-15 07:03

41 楼

O(n), 不知道有没有bug。
头尾两个index，头部发现偶数就与尾部发现奇数对换。直到头尾的index接触。
此时，奇偶的顺序已经调整完毕，需要恢复原来数据顺序。
从发现第一个偶数的位置与碰触点之间的数据反转。
从碰触点到尾部最后一个奇数位置之间的数据反转。
至此，原数据顺序恢复完毕。
public static void Swap(int[] arr, int index1, int index2)
{
int temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
public static int[] SortOddEven(int[] arr)
{
int indexOdd = 0;
int indexEven = arr.Length - 1;
int firstEven = 0;
while ((firstEven < arr.Length)&&(arr[firstEven] % 2 == 1))
firstEven ++;
int lastOdd = arr.Length - 1;
while ((lastOdd >= 0)&&(arr[lastOdd] % 2 == 0))
lastOdd --;
if ((firstEven < arr.Length - 1) && (lastOdd > 0))
{
int oddIndex = firstEven;
int evenIndex = lastOdd;
while (oddIndex < evenIndex)
{
Swap(arr, oddIndex, evenIndex);
while (arr[oddIndex] % 2 == 1)
oddIndex++;
while (arr[evenIndex] % 2 == 0)
evenIndex--;
}
for (int i = 0; i <= (oddIndex - 1 - firstEven) / 2; i++)
Swap(arr, firstEven + i, oddIndex - 1 - i);
for (int i = 0; i < (lastOdd - evenIndex - 1) / 2; i++)
Swap(arr, lastOdd - i, evenIndex + 1 + i);
}
return arr;
}

j*y2014-03-15 07:03

42 楼

bless.
没问老印怎么做吗？

【在 u*l 的大作中提到】

u*l2014-03-15 07:03

43 楼

input: 4,3,6,2,5
output (first step): 5,3,6,2,4
output final: 3,5,2,6,4 (?)
correct: 3,5,4,6,2

【在 y****n 的大作中提到】

: O(n), 不知道有没有bug。
: 头尾两个index，头部发现偶数就与尾部发现奇数对换。直到头尾的index接触。
: 此时，奇偶的顺序已经调整完毕，需要恢复原来数据顺序。
: 从发现第一个偶数的位置与碰触点之间的数据反转。
: 从碰触点到尾部最后一个奇数位置之间的数据反转。
: 至此，原数据顺序恢复完毕。
: public static void Swap(int[] arr, int index1, int index2)
: {
: int temp = arr[index1];
: arr[index1] = arr[index2];

u*l2014-03-15 07:03

44 楼

问了，老印集里哇啦的一通，没有听懂。

【在 j*****y 的大作中提到】

: bless.
: 没问老印怎么做吗？

j*y2014-03-15 07:03

45 楼

看来老印的方法也不简单

【在 u*l 的大作中提到】

: 问了，老印集里哇啦的一通，没有听懂。

w*x2014-03-15 07:03

46 楼

太难了，你看他面一年能找出一个写对nlogn解法的candidate

【在 u*l 的大作中提到】

: 问了，老印集里哇啦的一通，没有听懂。

y*n2014-03-15 07:03

47 楼

嗯，我想错了。谢谢指正！

【在 u*l 的大作中提到】

: input: 4,3,6,2,5
: output (first step): 5,3,6,2,4
: output final: 3,5,2,6,4 (?)
: correct: 3,5,4,6,2

e*e2014-03-15 07:03

48 楼

这题用partition + merge搞是nlog(n)吧。
T(n) = 2T(n/2) + n, 用主定理算出来是nlog(n).

【在 u*l 的大作中提到】

j*y2014-03-15 07:03

49 楼

merge 能 in-place 吗？

【在 e****e 的大作中提到】

: 这题用partition + merge搞是nlog(n)吧。
: T(n) = 2T(n/2) + n, 用主定理算出来是nlog(n).

n*t2014-03-15 07:03

50 楼

什么SB问题啊。

【在 u*l 的大作中提到】

l*b2014-03-15 07:03

51 楼

看着好难。。。

H*s2014-03-15 07:03

52 楼

这题我记得最近几年内以板上讨论过好几次了，好像从来没有人能做到的。
以前的题是 [a1, b1, a2, b2, a3, b3] --> [a1, a2, a3, b1, b2, b3]
或者反过来。可是从来就没有见过O(n)， in-place 的算法的。

【在 n******t 的大作中提到】

: 什么SB问题啊。

e*e2014-03-15 07:03

53 楼

: merge 能 in-place 吗？

c*t2014-03-15 07:03

54 楼

想了半天没想通
能给一下
a1,b1,a2,b2,a3,b3,a4,b4,a5,b5
的运行过程吗？
多谢！

【在 l***i 的大作中提到】

: divide and conquer, split at half, recurse, then swap mid part
: a1, b1, a2, b2, a3, b3
: a1, a2, b1 || a3, b2, b3
: a1, a2, a3, b1, b2, b3

H*s2014-03-15 07:03

55 楼

这样是可以in-place，可是O(n)做不到吧！

和3

【在 e****e 的大作中提到】

: 对这道题，可以吧! i.e.
: 5,6,8,2,3,9,4
: 5,6,8,2|3,9,4 第一次partition之后的样子。
: 5,6|8,2|3,9|4 第二次partition之后的样子。
: 现在可以开始merge了。
: 5,6|8,2|3,9|4 第一次merge之后的样子. 数的位置都挺好，不做任何变动。
: 5,6,8,2|3,9,4 第二次merge之后的样子. 数的位置都挺好，不做任何变动。
: 5,3,9,6,8,2,4 第三次merge之后的样子. 目标是不用额外的空间,如何就能把6,8,2和3
: ,9交换位置。
: 具体merge过程如下，可以先把2和3交换位置，再把2和9交换位置，交换之后的样子

l*b2014-03-15 07:03

56 楼

这样也不是 in place呀，每一个divide的分隔符都是要占空间的，像递归调用的stack
一样。。。

【在 H****s 的大作中提到】

: 这样是可以in-place，可是O(n)做不到吧！
:
: 和3

e*e2014-03-15 07:03

57 楼

请看我本主题第一个回贴，链接如下，上面说的确实是O(nlog(n))。我回答可以，是回
答问题“merge 能 in-place 吗？”。
http://www.mitbbs.com/article/JobHunting/32310263_0.html

【在 H****s 的大作中提到】

: 这样是可以in-place，可是O(n)做不到吧！
:
: 和3

e*e2014-03-15 07:03

58 楼

这个单竖线分割符是逻辑上的。。。，我在的例子中表示出来主要是为了看起来容易区
别前后两部分。实际partition的时候，partition的位置，是（startIndex+endIndx）
/2 算出来的，这个位置是前半部分的最后一个元素的位置。

stack

【在 l*******b 的大作中提到】

: 这样也不是 in place呀，每一个divide的分隔符都是要占空间的，像递归调用的stack
: 一样。。。

s*n2014-03-15 07:03

59 楼

两个指针从头到尾走一遍就好了 O(n) in place.
in the example, A = {5,6,8,3,9,2,4}, define 2 index odd = 0, even = 0;
when odd = 3, even = 1, swap(A[odd], A[even]); then A = {5,3,8,6,9,2,4}, at
this point, A[3] = 6, it is wrong, but the next step, we will swap it back
to A[2]
while(even < odd) even++; when even = 2, odd = 3 swap(A[odd], A[even]);Now
we got A = {5,3,6,8,9,2,4}
Got it..

j*y2014-03-15 07:03

60 楼

How do you handle B = {5, 6, 8, 10, 12, 3, 9, 2, 4} ? Thanks.

at

【在 s*******n 的大作中提到】

: 两个指针从头到尾走一遍就好了 O(n) in place.
: in the example, A = {5,6,8,3,9,2,4}, define 2 index odd = 0, even = 0;
: when odd = 3, even = 1, swap(A[odd], A[even]); then A = {5,3,8,6,9,2,4}, at
: this point, A[3] = 6, it is wrong, but the next step, we will swap it back
: to A[2]
: while(even < odd) even++; when even = 2, odd = 3 swap(A[odd], A[even]);Now
: we got A = {5,3,6,8,9,2,4}
: Got it..

e*e2014-03-15 07:03

61 楼

这个方法可行，谁能说说是不是O(n), 为什么是O(n)?
思路是: 维护这样一个数组，最左边是数是奇数，然后是偶数，之后是还没有处理的数。
i.e
3,7,5,1,9|4,6,2,8|3,8,7 某个时候数组的样子,下一步该处理数字3了。
3,7,5,1,9,3|4,6,2,8|8,7 处理了3之后的样子，下一步该处理数字8了
3,7,5,1,9,3|4,6,2,8,8|7 处理了8之后的样子，下一步该处理数字7了。
3,7,5,1,9,3,7|4,6,2,8,8 处理结束。
由此可以看到，每次处理时遇见偶数，我们什么都不用做，直接走去下一个位置；当处
理奇数，就要把所有的偶数右移一格，为这个奇数腾出一个位置，然后把奇数放进去。
Best Case: 奇数都在左边，偶数都在右边，只是traverse,其他什么都不用做。O(n)
time.
Worst Case: 于Best case的情况正好相反，每次都要右移全部的偶数。(n^2)?
Average Case: ? 谁来分析一下？

at

【在 s*******n 的大作中提到】

j*y2014-03-15 07:03

62 楼

这样是 n^2

数。

【在 e****e 的大作中提到】

: 这个方法可行，谁能说说是不是O(n), 为什么是O(n)?
: 思路是: 维护这样一个数组，最左边是数是奇数，然后是偶数，之后是还没有处理的数。
: i.e
: 3,7,5,1,9|4,6,2,8|3,8,7 某个时候数组的样子,下一步该处理数字3了。
: 3,7,5,1,9,3|4,6,2,8|8,7 处理了3之后的样子，下一步该处理数字8了
: 3,7,5,1,9,3|4,6,2,8,8|7 处理了8之后的样子，下一步该处理数字7了。
: 3,7,5,1,9,3,7|4,6,2,8,8 处理结束。
: 由此可以看到，每次处理时遇见偶数，我们什么都不用做，直接走去下一个位置；当处
: 理奇数，就要把所有的偶数右移一格，为这个奇数腾出一个位置，然后把奇数放进去。
: Best Case: 奇数都在左边，偶数都在右边，只是traverse,其他什么都不用做。O(n)

e*e2014-03-15 07:03

63 楼

5, 6, 8, 10, 12, 3, 9, 2, 4 处理5之前的样子。
5| 6, 8, 10, 12, 3, 9, 2, 4 处理5之后的样子，下一步该处理数字6了。
5| 6| 8, 10, 12, 3, 9, 2, 4 处理6之后的样子，下一步该处理数字8了。
此处省略处理数字10， 12时的样子，因为什么都没变，样子都一样。
5| 6, 8, 10, 12| 3, 9, 2, 4 处理12之后的样子，下一步该处理数字3了。
5, 3| 6, 8, 10, 12| 9, 2, 4 处理3之后的样子，下一步该处理数字9了。
5, 3, 9| 6, 8, 10, 12| 2, 4 处理9之后的样子，下一步该处理数字2了。
5, 3, 9| 6, 8, 10, 12, 2| 4 处理2之后的样子，下一步该处理数字4了。
5, 3, 9| 6, 8, 10, 12, 2, 4|
请注意单竖线分隔符，第一个表示处理过的奇数的边界位置，第二个表示处理过的偶数
的边界位置，第二个分隔符后的第一个数也是待处理的第一个数。

【在 j*****y 的大作中提到】

: How do you handle B = {5, 6, 8, 10, 12, 3, 9, 2, 4} ? Thanks.
:
: at

j*y2014-03-15 07:03

64 楼

这个是work的，和 insertion sort一样的思路，复杂度是 O(n^2)

【在 e****e 的大作中提到】

: 5, 6, 8, 10, 12, 3, 9, 2, 4 处理5之前的样子。
: 5| 6, 8, 10, 12, 3, 9, 2, 4 处理5之后的样子，下一步该处理数字6了。
: 5| 6| 8, 10, 12, 3, 9, 2, 4 处理6之后的样子，下一步该处理数字8了。
: 此处省略处理数字10， 12时的样子，因为什么都没变，样子都一样。
: 5| 6, 8, 10, 12| 3, 9, 2, 4 处理12之后的样子，下一步该处理数字3了。
: 5, 3| 6, 8, 10, 12| 9, 2, 4 处理3之后的样子，下一步该处理数字9了。
: 5, 3, 9| 6, 8, 10, 12| 2, 4 处理9之后的样子，下一步该处理数字2了。
: 5, 3, 9| 6, 8, 10, 12, 2| 4 处理2之后的样子，下一步该处理数字4了。
: 5, 3, 9| 6, 8, 10, 12, 2, 4|
: 请注意单竖线分隔符，第一个表示处理过的奇数的边界位置，第二个表示处理过的偶数

e*e2014-03-15 07:03

65 楼

我觉得也是，那就是没有partition+merge方法快了。但是是新方法，我觉得挺好的方
法，谢谢sumperman提供新思路。

【在 j*****y 的大作中提到】

: 这样是 n^2
:
: 数。

e*e2014-03-15 07:03

66 楼

是insertion sort的思路，谢谢你提供 O(n^2)的依据。

【在 j*****y 的大作中提到】

: 这个是work的，和 insertion sort一样的思路，复杂度是 O(n^2)

h*o2014-03-15 07:03

67 楼

不是 2 pointer吗？

【在 u*l 的大作中提到】

s*n2014-03-15 07:03

68 楼

如果非要O(n) in place, 看来只能借助system stack了，也就是说recusive调用的
stack不算addtional space.
For example, A = {2,3,6,7,4,5,8,10}
void oddeven(int[] a, int index, int oddpos){
if(index >= a.length){
把所有的偶数swap到数组的最右侧，O(n) time.
A = {7,3,5,2,6,4,8,10}
}

if(a[index]%2 == 1){
int odd = a[index];
oddeven(a, index + 1, oddpos + 1);
a[oddpos] = odd;
}else{
oddeven(a, index + 1, oddpos);
}
}
should work...

at

【在 s*******n 的大作中提到】

t*22014-03-15 07:03

69 楼

用两个指针，一头一尾，不是很容易？

t*22014-03-15 07:03

70 楼

想错了，难在还要保持相对顺序！

【在 t*********2 的大作中提到】

: 用两个指针，一头一尾，不是很容易？

e*e2014-03-15 07:03

71 楼

我不明白。。。
首先，用你的odd/even two pointers从数组第一个元素遍历完，得到的结果应该是
A = {7,3,5,2,4,6,8,10}，可以看出有些偶数位置也是错的。
其次，看不出为什么用stack，从例子可以看出，奇数的所在位置并不是正好和预期结
果是逆序。
最后，用了stack,并且存放奇数，就是需要额外的O(n)空间了。
你这个用recursion作为可利用的额外空间的想法挺好，应该有些题可以借鉴，虽然我
没有在你的方法里看到recursion函数和函数调用。。。

positions

【在 s*******n 的大作中提到】

: 如果非要O(n) in place, 看来只能借助system stack了，也就是说recusive调用的
: stack不算addtional space.
: For example, A = {2,3,6,7,4,5,8,10}
: void oddeven(int[] a, int index, int oddpos){
: if(index >= a.length){
: 把所有的偶数swap到数组的最右侧，O(n) time.
: A = {7,3,5,2,6,4,8,10}
: }
:
: if(a[index]%2 == 1){

s*n2014-03-15 07:03

72 楼

嗯，我修改了一下，should be clear now...

【在 e****e 的大作中提到】

: 我不明白。。。
: 首先，用你的odd/even two pointers从数组第一个元素遍历完，得到的结果应该是
: A = {7,3,5,2,4,6,8,10}，可以看出有些偶数位置也是错的。
: 其次，看不出为什么用stack，从例子可以看出，奇数的所在位置并不是正好和预期结
: 果是逆序。
: 最后，用了stack,并且存放奇数，就是需要额外的O(n)空间了。
: 你这个用recursion作为可利用的额外空间的想法挺好，应该有些题可以借鉴，虽然我
: 没有在你的方法里看到recursion函数和函数调用。。。
:
: positions

e*e2014-03-15 07:03

73 楼

我觉得还不怎么对。你走几个简单例子试试看就知道了。

【在 s*******n 的大作中提到】

: 嗯，我修改了一下，should be clear now...

n*e2014-03-15 07:03

74 楼

其实你都这样了，不如直接new一个array，
扫一遍原array，odd从头到尾放入新array，even从尾往头放入新array。
然后按顺序把新array的值压回原array。。。

【在 s*******n 的大作中提到】

e*e2014-03-15 07:03

75 楼

赞同。不过因为“even从尾往头放入新array”，完了之后，偶数部分是正确期望答案
的逆序，所以还要in-place reverse偶数部分。然后销毁原数组，直接返回这个新数组
。除了不满足原题要求的in-place,之外，其他方面题目要求都达到了。。。

【在 n***e 的大作中提到】

: 其实你都这样了，不如直接new一个array，
: 扫一遍原array，odd从头到尾放入新array，even从尾往头放入新array。
: 然后按顺序把新array的值压回原array。。。

l*b2014-03-15 07:03

76 楼

这个就是counting sort呀.. 呵呵
这个in place看起来太难搞了

【在 n***e 的大作中提到】

: 其实你都这样了，不如直接new一个array，
: 扫一遍原array，odd从头到尾放入新array，even从尾往头放入新array。
: 然后按顺序把新array的值压回原array。。。

i*72014-03-15 07:03

77 楼

我觉得是故意要刷LZ的。我相信这一题没有那个人要的答案。

b*32014-03-15 07:03

78 楼

想了一下这个题目，应该充分利用双向链表的条件，分2步完成，第一步扫描整个双向
链表，如果是奇数就用next链接，如果是偶数就有previous链接，第二部把奇数链表和
偶数链表交换到相应位置。第一步中previous与next一样，只是我们换了叫它previous
而已。
2 3 4 5 2 - 4 3 -5
3 = 5 = 2 = 4
时间复杂度o(n),空间复杂度o(1)

u*l2014-03-15 07:03

79 楼

如果Input就是双向链表，倒是可以。
如果Input是Array，就不行了。

previous

【在 b*******3 的大作中提到】

: 想了一下这个题目，应该充分利用双向链表的条件，分2步完成，第一步扫描整个双向
: 链表，如果是奇数就用next链接，如果是偶数就有previous链接，第二部把奇数链表和
: 偶数链表交换到相应位置。第一步中previous与next一样，只是我们换了叫它previous
: 而已。
: 2 3 4 5 2 - 4 3 -5
: 3 = 5 = 2 = 4
: 时间复杂度o(n),空间复杂度o(1)

b*32014-03-15 07:03

80 楼

看错了题设，把这个题与另外一个题目混淆了，很奇怪找不到了，我觉得这个应该就是
那个双向链表那题的答案。

Y*Y2014-03-15 07:03

81 楼

这个单向链表就可以吧.这个题误导性太强，很容易往partition上想，昨天晚上想了半
天的partition/sorting. 后来发现其实很简单。面试时要碰到基本上完蛋。
scan一遍,把even number分出去，成另外一个链表；然后把两个链表接起来。
input: 2 -> 3 -> 6 -> 7 -> 4 -> 5 -> 8 -> 10
第一步：3->7->5
2->6->4->8->10
第二步：3->7->5->2->6->4->8->10
list * sort_odd_even(list* head) {
list *odd_head;
list *even_head, *even;
list *current, *previous;
if (!head || !head->next) {
return head;
}

previous = 0;
current = head;

while (current) {
if (current->value%2==0) { /*even number*/
if (!even_head) {
even_head = even = current;
} else {
even->next = current;
even = even->next;
}

if (previous) {
previous->next = current->next;
}
current = current->next;
even->next = 0;
} else {
if (!odd_head) {
odd_head = current;
}
previous = current;
current = current->next;
}
if (!odd_head) {
return even_head;
}

previous->next = even_head;

return odd_head;
}

m*i2014-03-15 07:03

82 楼

建议可以用这个题目面3哥

o*n2014-03-15 07:03

83 楼

但老印给的signature说了是array，你用linked list，那不就是extra space吗?

b*g2014-03-15 07:03

84 楼

void oddBeforeEven(int arr[], long N)
{
int count[2];
for (long k = 0; k < 2; ++k) count[k] = 0;
for (long i = 0; i < N; ++i)
if (arr[i] & 1) count[1]++

int *buffer = new int[N];
for (long i = 0; i< N; ++i)
buffer[i] = arr[i];
for (long i =0; i < N; ++i)
{ // even number will be at postion count[1], count[1] + 1, count[1]
+2, ......
if (buffer[i] & 1) arr[count[0]++] = buffer[i];
else arr[count[1]++] = buffer[i];
}
delete[] buffer;
}

【在 u*l 的大作中提到】

b*g2014-03-15 07:03

85 楼

没看到 inplace，我再想想

【在 b******g 的大作中提到】

: void oddBeforeEven(int arr[], long N)
: {
: int count[2];
: for (long k = 0; k < 2; ++k) count[k] = 0;
: for (long i = 0; i < N; ++i)
: if (arr[i] & 1) count[1]++
:
: int *buffer = new int[N];
: for (long i = 0; i< N; ++i)
: buffer[i] = arr[i];

Y*Y2014-03-15 07:03

86 楼

回错主题了，有另外一贴double link list奇偶排序的。原帖删了。
数组的这个想出了一个nlogn的in place方法
1. 每两个数一组，每组内变成odd/even order，最后一组可以小一些。
2. Repeat: 上次的每两组合并, 前组后面的even numbers和后组前面的odd numbers换
位。直到合成一组。
Complexity: O(2)*n/2+O(4)*n/4+ ...+ O(n) = nlogn
长度不同的组换位：
For example, swap {1...m} with {m+1 ... n} assuming m>n.
swap {1 ... n} with {m+1 ... m+n},
then the problem is reduced to swap {n+1 ...m} and {m+1...m+n}
Complexity: f(m+n) = O(n)+f(m) = O(m+n)

【在 o********n 的大作中提到】

: 但老印给的signature说了是array，你用linked list，那不就是extra space吗?

O*i2014-03-15 07:03

87 楼

我记得以前讨论过，当时是正数，负数，要求只扫一遍。
这里是奇数，偶数。
记得当时没有人想到O(n)的解法的，这题纯粹是老印要为难你。