昨天有人在在首页发了一个号称是百度的面试题，题目如下：
百度面试题（一）：假设一整型数组存在若干正数和负数，现在通过某种算法使得该数组的所有负数在正数的左边，且保证负数和正数间元素相对位置不变。时空复杂度要求分别为：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;
}
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。