微软intern面经，求答案

is that in this way?
Firstly find the number of positive and negtive numbers, then exchange corresponding positions.
I think it is O(n)

回复 7# wwwyhx

为什么校园面试就碰到这种题……

回复 9# rayray81502

这样顺序是会乱的

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

回复 11# bingjie

是会乱序的吧

没思路, 不会做

贴下版大发的习题里面的M12.h。
没细看，供大家参考：

1. //Given an array of positive and negative integers, re-arrange it
   
2. //so that you have postives on one end and negatives on the other,
   
3. //BUT retain the original order of appearance.
   
4. //For eg. 1, 7, -5, 9, -12, 15 => -5, -12, 1, 7, 9, 15
   
5. 
   
6. // There is a solution which took O(n) space and O(n) time which is simple
   
7. // Below is a solution which adopt the concept of merge so the time cost is
   
8. // O(nlogn) and space O(1)
   
9. // Below is the merge sort solution, notice that if you want to turn -1,-2,3,4,5
   
10. // to 3,4,5,-1,-2, you need to reverse the whole array, that's to 5,4,3,-2,-1; and for
    
11. // the two segment, reverse each segment back. So, first reversion come to 3,4,5,-2,-1,
    
12. // last reversion come to 3,4,5,-1,-2 which is the resilt you want
    
13. 
    
14. void Rearrange(int a[], int n)
    
15. {
    
16.         assert(n>0);
    
17.         if (1 == n) return;
    
18. 
    
19.         if (2 == n)
    
20.         {
    
21.                 if (a[0]>=0 && a[1]<0)
    
22.                 {
    
23.                         int tmp = a[0];
    
24.                         a[0] = a[1];
    
25.                         a[1] = tmp;
    
26.                 }
    
27. 
    
28.                 return;
    
29.         }
    
30. 
    
31.         int nLft = n/2;
    
32.         int nRgt = n-nLft;
    
33.         int* pLft = a;
    
34.         int* pRgt = a+nLft;
    
35.         Rearrange(pLft, nLft);
    
36.         Rearrange(pRgt, nRgt);
    
37. 
    
38.         int* pIterL = pLft;
    
39.         int* pIterR = pRgt;
    
40.         while (*pIterL < 0 && pIterL-pLft<nLft) pIterL++;
    
41.         while (*pIterR < 0 && pIterR-pRgt<nRgt) pIterR++;
    
42.        
    
43.         pIterR--;
    
44.         int* pTmpL = pIterL;
    
45.         int* pTmpR = pIterR;
    
46.         while (pTmpL < pTmpR)
    
47.         {
    
48.                 int tmp = *pTmpL;
    
49.                 *pTmpL = *pTmpR;
    
50.                 *pTmpR = tmp;
    
51.                 pTmpL++;
    
52.                 pTmpR--;
    
53.         }
    
54. 
    
55.         int* pIterLEnd = pIterL+(pIterR-pRgt);
    
56.         int* pIterRBeg = pIterLEnd+1;
    
57.         pTmpL = pIterL;
    
58.         pTmpR = pIterLEnd;
    
59.         while (pTmpL < pTmpR)
    
60.         {
    
61.                 int tmp = *pTmpL;
    
62.                 *pTmpL = *pTmpR;
    
63.                 *pTmpR = tmp;
    
64.                 pTmpL++;
    
65.                 pTmpR--;
    
66.         }
    
67. 
    
68.         pTmpL = pIterRBeg;
    
69.         pTmpR = pIterR;
    
70.         while (pTmpL < pTmpR)
    
71.         {
    
72.                 int tmp = *pTmpL;
    
73.                 *pTmpL = *pTmpR;
    
74.                 *pTmpR = tmp;
    
75.                 pTmpL++;
    
76.                 pTmpR--;
    
77.         }
    
78. }
    
79. 
    
80. void test()
    
81. {
    
82.         int a[] = {1,-3, 56, 7, -5, 9, -12, 15};
    
83.         Rearrange(a, sizeof(a)/sizeof(int));
    
84.         for (int i = 0; i < sizeof(a)/sizeof(int); i++)
    
85.         {
    
86.                 cout<<a[i]<<" ";
    
87.         }
    
88.         cout<<endl;
    
89. }

复制代码

题目稍有变化，版大给的题目是要求负数在前面，这个相反，供大家参考了！

回复 17# tsy3602

递归仍能保持O（1）？stack当中的空间不计入么？

回复 18# smzfeng


    应该是这么理解了...具体问版大，他写的程序！！

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies