推荐订阅源

昨天有人在在首页发了一个号称是百度的面试题，题目如下：

    百度面试题（一）：假设一整型数组存在若干正数和负数，现在通过某种算法使得该数组的所有负数在正数的左边，且保证负数和正数间元素相对位置不变。时空复杂度要求分别为：o(n)和o(1)。 

 当晚在家研究了一个小时，无解。。 

o(n)和o(1)。

且保证负数和正数间元素相对位置不变，这三个条件去掉哪个都很好实现。今天早上，楼主突然宣布，没有

“且保证负数和正数间元素相对位置不变 ”  这个条件，我晕死！

去掉第三个条件实现起来就非常简单了，代码如下：

void Main()
{
    int[] arr=  {-1,1,-4,5,-2,9,8,2,-6};
    int insertPos = 0;
    
    while(arr[insertPos] < 0 ) insertPos++; // 先找到第一个负数，如果以正数开头，测从第一位开始插入
    
    int begPos = insertPos+1;
    
    while(begPos < arr.Length)
    {
        if (arr[begPos] < 0)
        {
            swap(arr,begPos,insertPos);
            insertPos++;
        }
        begPos ++;
    }
    
    arr.Dump();
}void swap(int[] arr,int i,int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;

}