logo
Redian新闻
>未名空间
>Parenting - 为人父母
>
四岁的男孩和爸妈一起特别害羞，可是如果爸妈不在身边特别social,这是什么原因啊
avatar
四岁的男孩和爸妈一起特别害羞，可是如果爸妈不在身边特别social,这是什么原因啊# Parenting - 为人父母
x*o
1 楼
结婚半年，跟着ld过来三个月了，是J2。现在只上了ESL，其余的时间呆家里的多。虽
然不讨厌做饭，收拾家务，但也总想利用这里的机会提升一下自己，将来回国了找工作
什么的也容易些。
1.读书。如果我不想和ld两地的话，我该申请什么学校呢？还是在就近的学校辅修一些
专业？
2.工作。没有美国本土文凭，肯定不好找吧？再者，我们的地方很偏，根本没有太多的
单位。
3.安心做housewife,然后计划要娃。
想问问跟我经历相似的人，你们是怎么过来的？
avatar
u*l
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).
avatar
n*e
3 楼
是我们自己教育方法有问题吗？为什么孩子有父母在旁边很放不开呢。。。
avatar
V*8
4 楼
I would choose #1.
Financial independence is the key, going back to school gets you on the
right track.
avatar
w*x
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);
}
avatar
x*o
6 楼
很喜欢你的头像，超可爱；）
如果申请读研的话，那很可能得两地吧？要真这样了，那感觉就是走了另一条路了。

【在 V*****8 的大作中提到】
: I would choose #1.
: Financial independence is the key, going back to school gets you on the
: right track.
avatar
u*l
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);
avatar
k*e
8 楼
如果30了，就要孩子。不过还不到30，就读书或者工作
如果本科学历以下，就读书
如果国内有工作经验，英语尚好，就找工作试试看

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

nlogn 吧

【在 u*l 的大作中提到】
: 你的这个计算复杂度是多少？
: O(N) or O(Lgn)?
avatar
V*8
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 的大作中提到】
: 很喜欢你的头像，超可爱；）
: 如果申请读研的话，那很可能得两地吧？要真这样了，那感觉就是走了另一条路了。
avatar
u*l
11 楼
人家（老印）面试官要O（N)

【在 w****x 的大作中提到】
:
: nlogn 吧
avatar
x*o
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.
avatar
c*t
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).
avatar
V*8
14 楼
Thank you very much, please vote for him at the link below!

【在 x******o 的大作中提到】
: 哇，没想到啊，我一看这么漂亮，以为是别处的图片什么的，mm好福气啊。
:
: choose
: kids,
avatar
m*s
15 楼
印象里是道恶心题。。。跟啥杨表求中位数之流一个味道。。。
实际上就是stable_partition，如果去翻各种c++ stl的实现，会发现用的是O(nlogn)
的分治，也是现实中最好用的。。。不过如果要追求O(n)，那就要翻paper了orz。读懂
了在面试中也说不明白。。。
在这个问题里，虽然数组元素是有限整数，不过我是看不出来有啥用处。。。

【在 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).
avatar
x*o
16 楼
俺已经投了嘿嘿。

【在 V*****8 的大作中提到】
: Thank you very much, please vote for him at the link below!
avatar
u*l
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];
avatar
b*r
18 楼
如果lg对你好的话，做家务生小孩也是很好的选择。
avatar
c*w
19 楼
你这个出来不是 [5,9,3,2,8,6,4] 吗？
avatar
l*c
20 楼
not the same sequence, no stable

【在 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];
avatar
c*t
21 楼
嗯，又土了

【在 u*l 的大作中提到】
: 顺序（Ordering)乱了吧？
avatar
t*h
22 楼
这不就是典型的partition吗？

【在 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).
avatar
c*t
23 楼
说实在，O(nlogn)我都想不出，阿三好狠的题。

【在 t*********h 的大作中提到】
: 这不就是典型的partition吗？
avatar
l*i
24 楼
被一个好人老印问过，写了个O(n^2)，之后说了O(nlogn)的思路，还表扬我算法好。这
个跟另一个题是一回事，
given a1,b1,a2,b2,a3,b3
transform into a1,a2,a3,b1,b2,b3
avatar
f*e
25 楼
这个题以前本版出现过，到底答案是什么？

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

【在 f*****e 的大作中提到】
: 这个题以前本版出现过，到底答案是什么？
avatar
f*e
27 楼
如果数的范围很小，就用高几位表示index，低几位表示value？
还是变相利用了额外空间。

【在 s****0 的大作中提到】
: 同问。
avatar
w*p
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 的大作中提到】
: 一个Array，比如A[]=[5,6,8,2,3,9,4]
: 输出要求是所有的奇数在偶数的前面，并保留相对顺序。
: output: [5,3,9,6,8,2,4].
: 老印面试官：要求：
: In-place (no additional place);
: 时间复杂度： O(N).
avatar
s*0
29 楼
不对吧。
再试试。。。

【在 f*****e 的大作中提到】
: 如果数的范围很小，就用高几位表示index，低几位表示value？
: 还是变相利用了额外空间。
avatar
d*x
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
avatar
t*h
31 楼
刚想了一个很简单的 发现部stable

【在 c********t 的大作中提到】
: 说实在，O(nlogn)我都想不出，阿三好狠的题。
avatar
f*e
32 楼
先都搞为正的，然后换成prefix sum，然后对prefix sum排序，再相减。

【在 t*********h 的大作中提到】
: 刚想了一个很简单的 发现部stable
avatar
t*h
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
avatar
w*p
34 楼
写的时候发现用quick sort 的partition, 还是有问题。
用merge sort 的partition. 速度在O(n) （最快）和O(logn) （wrose) 之间

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
avatar
c*t
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
avatar
h*n
36 楼
这个题我从来没见过stable，in place + O（n）的算法
怀疑根本就是不可能做到的事情，
这个题估计烙印就是专门要挂你吧，看似简单，其实不简单

【在 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).
avatar
h*n
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]);
avatar
w*p
38 楼
remember each position space 是O(N) ?

【在 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]);
avatar
t*h
39 楼
那没招了 放弃 烙印是来刷LZ的吧...

【在 h****n 的大作中提到】
: 你这已经不是inplace了，不能用额外空间
avatar
l*i
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),你是什么思路？
avatar
y*n
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;
}
avatar
j*y
42 楼
bless.
没问老印怎么做吗？

【在 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).
avatar
u*l
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];
avatar
u*l
44 楼
问了，老印集里哇啦的一通，没有听懂。

【在 j*****y 的大作中提到】
: bless.
: 没问老印怎么做吗？
avatar
j*y
45 楼
看来老印的方法也不简单

【在 u*l 的大作中提到】
: 问了，老印集里哇啦的一通，没有听懂。
avatar
w*x
46 楼

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

【在 u*l 的大作中提到】
: 问了，老印集里哇啦的一通，没有听懂。
avatar
y*n
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
avatar
e*e
48 楼
这题用partition + merge搞是nlog(n)吧。
T(n) = 2T(n/2) + n, 用主定理算出来是nlog(n).

【在 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).
avatar
j*y
49 楼
merge 能 in-place 吗？

【在 e****e 的大作中提到】
: 这题用partition + merge搞是nlog(n)吧。
: T(n) = 2T(n/2) + n, 用主定理算出来是nlog(n).
avatar
n*t
50 楼
什么SB问题啊。

【在 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).
avatar
l*b
51 楼
看着好难。。。
avatar
H*s
52 楼
这题我记得最近几年内以板上讨论过好几次了，好像从来没有人能做到的。
以前的题是 [a1, b1, a2, b2, a3, b3] --> [a1, a2, a3, b1, b2, b3]
或者反过来。可是从来就没有见过O(n)， in-place 的算法的。

【在 n******t 的大作中提到】
: 什么SB问题啊。
avatar
e*e
53 楼
对这道题，可以吧! 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交换位置，交换之后的样子
5,6,8|3,9,2,4
然后再交换6和3，8和9, 交换之后的样子。
5,3,9,6,8,2,4 最终答案！

【在 j*****y 的大作中提到】
: merge 能 in-place 吗？
avatar
c*t
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
avatar
H*s
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交换位置，交换之后的样子
avatar
l*b
56 楼
这样也不是 in place呀，每一个divide的分隔符都是要占空间的，像递归调用的stack
一样。。。

【在 H****s 的大作中提到】
: 这样是可以in-place， 可是O(n)做不到吧！
:
: 和3
avatar
e*e
57 楼
请看我本主题第一个回贴，链接如下，上面说的确实是O(nlog(n))。我回答可以，是回
答问题“merge 能 in-place 吗？”。
http://www.mitbbs.com/article/JobHunting/32310263_0.html

【在 H****s 的大作中提到】
: 这样是可以in-place， 可是O(n)做不到吧！
:
: 和3
avatar
e*e
58 楼
这个单竖线分割符是逻辑上的。。。，我在的例子中表示出来主要是为了看起来容易区
别前后两部分。实际partition的时候，partition的位置，是（startIndex+endIndx）
/2 算出来的，这个位置是前半部分的最后一个元素的位置。

stack

【在 l*******b 的大作中提到】
: 这样也不是 in place呀，每一个divide的分隔符都是要占空间的，像递归调用的stack
: 一样。。。
avatar
s*n
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..
avatar
j*y
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..
avatar
e*e
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 的大作中提到】
: 两个指针从头到尾走一遍就好了 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..
avatar
j*y
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)
avatar
e*e
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
avatar
j*y
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|
: 请注意单竖线分隔符，第一个表示处理过的奇数的边界位置，第二个表示处理过的偶数
avatar
e*e
65 楼
我觉得也是，那就是没有partition+merge方法快了。但是是新方法，我觉得挺好的方
法，谢谢sumperman提供新思路。

【在 j*****y 的大作中提到】
: 这样是 n^2
:
: 数。
avatar
e*e
66 楼
是insertion sort的思路，谢谢你提供 O(n^2)的依据。

【在 j*****y 的大作中提到】
: 这个是work的，和 insertion sort一样的思路， 复杂度是 O(n^2)
avatar
h*o
67 楼
不是 2 pointer吗？

【在 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).
avatar
s*n
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 的大作中提到】
: 两个指针从头到尾走一遍就好了 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..
avatar
t*2
69 楼
用两个指针， 一头一尾， 不是很容易？
avatar
t*2
70 楼
想错了，难在还要保持相对顺序！

【在 t*********2 的大作中提到】
: 用两个指针， 一头一尾， 不是很容易？
avatar
e*e
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){
avatar
s*n
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
avatar
e*e
73 楼
我觉得还不怎么对。你走几个简单例子试试看就知道了。

【在 s*******n 的大作中提到】
: 嗯，我修改了一下，should be clear now...
avatar
n*e
74 楼
其实你都这样了，不如直接new一个array，
扫一遍原array，odd从头到尾放入新array，even从尾往头放入新array。
然后按顺序把新array的值压回原array。。。

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

【在 n***e 的大作中提到】
: 其实你都这样了，不如直接new一个array，
: 扫一遍原array，odd从头到尾放入新array，even从尾往头放入新array。
: 然后按顺序把新array的值压回原array。。。
avatar
l*b
76 楼
这个就是counting sort呀.. 呵呵
这个in place看起来太难搞了

【在 n***e 的大作中提到】
: 其实你都这样了，不如直接new一个array，
: 扫一遍原array，odd从头到尾放入新array，even从尾往头放入新array。
: 然后按顺序把新array的值压回原array。。。
avatar
i*7
77 楼
我觉得是故意要刷LZ的。我相信这一题没有那个人要的答案。
avatar
b*3
78 楼
想了一下这个题目，应该充分利用双向链表的条件，分2步完成，第一步扫描整个双向
链表，如果是奇数就用next链接，如果是偶数就有previous链接，第二部把奇数链表和
偶数链表交换到相应位置。第一步中previous与next一样，只是我们换了叫它previous
而已。
2 3 4 5 2 - 4 3 -5
3 = 5 = 2 = 4
时间复杂度o(n),空间复杂度o(1)
avatar
u*l
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)
avatar
b*3
80 楼
看错了题设，把这个题与另外一个题目混淆了，很奇怪找不到了，我觉得这个应该就是
那个双向链表那题的答案。
avatar
Y*Y
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;
}
avatar
m*i
82 楼
建议可以用这个题目面3哥
avatar
o*n
83 楼
但老印给的signature说了是array，你用linked list，那不就是extra space吗?
avatar
b*g
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 的大作中提到】
: 一个Array，比如A[]=[5,6,8,2,3,9,4]
: 输出要求是所有的奇数在偶数的前面，并保留相对顺序。
: output: [5,3,9,6,8,2,4].
: 老印面试官：要求：
: In-place (no additional place);
: 时间复杂度： O(N).
avatar
b*g
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];
avatar
Y*Y
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吗?
avatar
O*i
87 楼
我记得以前讨论过，当时是正数，负数，要求只扫一遍。
这里是奇数，偶数。
记得当时没有人想到O(n)的解法的，这题纯粹是老印要为难你。
相关阅读
求问15岁男孩子的生日礼物宝宝care别人的反应怎么办宝宝每一分钟都在地上捡吃的怎么办？遇到无理取闹的小孩咋办滑轮鞋几岁可以上？不太会思考但是记性很好的娃，怎么引导一下呢？帖个各州法定允许孩子单独呆着的年龄限制。弱问加州高中的情况推荐一个LEGO 零件收纳盒 (转载)娃怎么学会自己玩caillou父母太宅怎么办？求助，宝宝从中国回来以后总是哭闹 (转载)有boston附近的需要breat milk的吗？请推荐小娃的first roller skate我现在在宠物店看到卖 training pad，狗用的......同事家生bb送啥合适？又来向有经验的爸爸妈妈请教了：daycare里儿歌主题的活动想起了我的一个小“情人”非要扯上道德，教育孩子孝顺是很自私的
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。