666
百度麵試題：求一個已排序的數組中絕對值最小的元素
題目為：有一個已經排序的數組（升序），數組中可能有正數、負數或0，求數組中元素的絕對值最小的數，要求，不能用順序比較的方法（複雜度需要小於O（n）），可以使用任何語言實現
例如，數組{-20，-13，-4, 6, 77,200} ，絕對值最小的是-4。
這一題該如何求呢？
初步的解決思路是：
1.數組中的元素全為正，取最左邊的數字；
2.數組中的元素全為負，取最右邊的數字的絕對值；
3.數組中有正數有負數，就用二分法查找，判斷中間元素的符號
a)中間元素為正，繼續判斷中間元素前麵一個元素的符號
b)中間元素為負，判斷中間元素後一個元素的符號
c)中間元素為零，令其等於結果值返回
下麵是根據上麵的想法的代碼實現，應該還會有漏洞
#include "stdafx.h"
#include <iostream>
using namespace std;
//求取數組中絕對值最小的數字
int minAbsolute(int arr[],int size);
//返回兩個數中較小的數
int compare(int a,int b);
int _tmain(int argc, _TCHAR* argv[])
{
int a[10] = {-10,-8,-5,-3,2,5,8,9,11,15};
int size = sizeof(a)/sizeof(int);
int result = minAbsolute(a,size);
cout<<"絕對值最小的數是："<<result<<endl;
return 0;
}
int minAbsolute(int arr[],int size)
{
int first,last,mid;
first = 0;
last = size - 1;
int result;
//數組中的數全是負數，取最右邊的數
if (arr[0] < 0 && arr[size-1] < 0)
{
result = arr[size-1];
}
//數組中的數全是正數，取最左邊的數
else if (arr[0] > 0 && arr[size-1] > 0)
{
result = arr[0];
}
//數組有正有負，二分查找
else
{
while(first < last)
{
int mid = (first + last)/2;
if (arr[mid] > 0)
{
if (arr[mid - 1] > 0)
{
last = mid - 1;
}
else if(arr[mid - 1] < 0)
{
result = compare(-arr[mid - 1],arr[mid]);
break;
}
else
{
result = arr[mid - 1];
break;
}
}
else if (arr[mid] < 0)
{
if (arr[mid + 1] < 0)
{
first = mid + 1;
}
else if (arr[mid + 1] > 0)
{
result = compare(-arr[mid],arr[mid+1]);
break;
}
else
{
result = arr[mid + 1];
break;
}
}
else
{
result = arr[mid];
break;
}
}
}
return result;
}
int compare(int a,int b)
{
if (a > b)
{
return b;
}
else
{
return a;
}
}
最後更新：2017-04-04 07:03:42