有一個(gè)已經(jīng)排序的數(shù)組（升序），數(shù)組中可能有正數(shù)、負(fù)數(shù)或0，求數(shù)組中元素的絕對(duì)值最小的數(shù)，要求，不能用順序比較的方法（復(fù)雜度需要小于O（n）），可以使用任何語(yǔ)言實(shí)現(xiàn)
例如，數(shù)組{-20，-13，-4, 6, 77,200} ，絕對(duì)值最小的是-4。
算法實(shí)現(xiàn)的基本思路
找到負(fù)數(shù)和正數(shù)的分界點(diǎn)，如果正好是0就是它了，如果是正數(shù)，再和左面相鄰的負(fù)數(shù)絕對(duì)值比較，如果是負(fù)數(shù)，取取絕對(duì)值與右面正數(shù)比較。還要考慮數(shù)組只有正數(shù)或負(fù)數(shù)的情況。
我根據(jù)這個(gè)思路用Java簡(jiǎn)單實(shí)現(xiàn)了一個(gè)算法。大家有更好的實(shí)現(xiàn)方法歡迎跟帖
public class MinAbsoluteValue
{
private static int getMinAbsoluteValue(int[] source)
{
int index = 0;
int result = 0;
int startIndex = 0;
int endIndex = source.length - 1;
// 計(jì)算負(fù)數(shù)和正數(shù)分界點(diǎn)
while(true)
{ // 計(jì)算當(dāng)前的索引
index = startIndex + (endIndex - startIndex) / 2;
result = source[index];<br> // 如果等于0，就直接返回了，0肯定是絕對(duì)值最小的
if(result==0)
{
return 0;
} // 如果值大于0，處理當(dāng)前位置左側(cè)區(qū)域，因?yàn)樨?fù)數(shù)肯定在左側(cè)
else if(result > 0)
{
if(index == 0)
{
break;
}
if(source[index-1] >0)
endIndex = index - 1;
else if(source[index-1] ==0)
return 0;
else
break;
} // 如果小于0，處理當(dāng)前位置右側(cè)的區(qū)域，因?yàn)檎龜?shù)肯定在右側(cè)的位置
else
{
if(index == endIndex)
break;
if(source[index + 1] < 0)
startIndex = index + 1;
else if(source[index + 1] == 0)
return 0;
else
break;
}
}
// 根據(jù)分界點(diǎn)計(jì)算絕對(duì)值最小的數(shù)
if(source[index] > 0)
{
if(index == 0 || source[index] < Math.abs(source[index-1]))
result= source[index];
else
result = source[index-1];
}
else
{
if(index == source.length - 1 || Math.abs(source[index]) < source[index+1])
result= source[index];
else
result = source[index+1];
}
return result;
}
public static void main(String[] args) throws Exception
{
int[] arr1 = new int[]{-23,-22,-3,-2,1,2,3,5,20,120};
int[] arr2 = new int[]{-23,-22,-12,-6,-4};
int[] arr3 = new int[]{1,22,33,55,66,333};
int value = getMinAbsoluteValue(arr1);
System.out.println(value);
value = getMinAbsoluteValue(arr2);
System.out.println(value);
value = getMinAbsoluteValue(arr3);
System.out.println(value);
}
}
新浪微博：http://t.sina.com.cn/androidguy 昵稱(chēng)：李寧_Lining