算法--兩道百度筆試題
今天看到一位園友寫了一篇關于百度的面試題的博客，成了評論頭條，再下看了一下，非常感興趣，那位博主的算法能力跟我一樣需要提高，估計他的功力還在我之下，所以再下不才，在這里把自己的源碼貼出來。
百度面試題（一）：假設一整型數組存在若干正數和負數，現在通過某種算法使得該數組的所有負數在正數的左邊，且保證負數和正數間元素相對位置不變。時空復雜度要求分別為：o(n)和o(1)。
其實開始的時候我也是一頭霧水，在紙上畫畫之后發現，其實就是一道變形的插入排序。幸運的是這里不需要比較大小，要比較大小的話時間復雜度是O(n2),只用判斷正負，那時間復雜度就只要O(n)了。
如：-3,1,2，-1，-3,4。其實就是把正數后面的第一個負數（如-1）插到第一個正數(1)的前面，負數之間的每個正數(1,2)后移一位，就這么簡單。時間復雜度剛好為O(n),控件復雜度為O(1)。
//算法分開正負數
void insertSort(int*A ,int size)
{
int minus=-1,plus=-1;
int tmp=0;
for(int i=0;i<size;i++)
{
if(minus==-1)
{
if(A[i]<0&& plus>=0)
{
minus=i;
}
if(A[i]>0&& plus<0)
{
plus=i;
}
}
if(minus>=0&& plus>=0)
{
tmp=A[plus];
A[plus++] = A[minus];
for (int k = minus; k> plus; k--)
{
A[k] = A[k -1];
}
A[plus]=tmp;
minus=-1;
}
}
}
百度面試題（二），給定一個存放正數的數組，重新排列數組使得數組左邊為奇數，右邊為偶數，且保證奇數和偶數之間元素相對位置不變。時空復雜度要求分別為：o(n)和o(1)。
其實這兩道筆試題沒有什么區別，要說有區別就是看你是否理解。
//算法分開奇偶數
void insertSort1(int*A ,int size)
{
int minus=-1,plus=-1;
int tmp=0;
for(int i=0;i<size;i++)
{
if(minus==-1)
{
if(A[i]%2!=0&& plus>=0)
{
minus=i;
}
if(A[i]%2==0&& plus<0)
{
plus=i;
}
}
if(minus>=0&& plus>=0)
{
tmp=A[plus];
A[plus++] = A[minus];
for (int k = minus; k> plus; k--)
{
A[k] = A[k -1];
}
A[plus]=tmp;
minus=-1;
}
}
}
測試代碼如下：
//測試代碼
int main() {
int A[]={2,1,-2,12,4,-2,-4,-6 };
int size=sizeof(A)/sizeof(int);
cout<<"-----------------------算法分開正負數-----------------------"<<endl;
for(int i=0;i<size;i++)
{
cout<<A[i]<<"\t";
}
cout<<endl;
insertSort(A,size);
for(int i=0;i<size;i++)
{
cout<<A[i]<<"\t";
}
cout<<endl;
cout<<endl;
cout<<"-----------------------算法分開奇偶數-----------------------"<<endl;
int B[]={2,1,-2,12,4,-2,-4,-6};
int s=sizeof(B)/sizeof(int);
for(int i=0;i<s;i++)
{
cout<<B[i]<<"\t";
}
cout<<endl;
insertSort1(B,s);
for(int i=0;i<s;i++)
{
cout<<B[i]<<"\t";
}
getchar();
return0;
}
運行結構截圖：
作者：陳太漢
浙公網安備 33010602011771號