百度面试题：求绝对值最小的数
百度面试题：求绝对值最小的数
有一个已经排序的数组（升序），数组中可能有正数、负数或0，求数组中元素的绝对值最小的数，要求，不能用顺序比较的方法（复杂度需要小于O（n）），可以使用任何语言实现
例如，数组{-20，-13，-4, 6, 77,200} ，绝对值最小的是-4。
算法实现的基本思路
找到负数和正数的分界点，如果正好是0就是它了，如果是正数，再和左面相邻的负数绝对值比较，如果是负数，取取绝对值与右面正数比较。还要考虑数组只有正数或负数的情况。
我根据这个思路用Java简单实现了一个算法。 大家有更好的实现方法欢迎跟帖
public class MinAbsoluteValue
{
private static int getMinAbsoluteValue( int [] source)
{
int index = 0 ;
int result = 0 ;
int startIndex = 0 ;
int endIndex = source.length - 1 ;
// 计算负数和正数分界点
while ( true )
{<br> // 计算当前的索引
index = startIndex + (endIndex - startIndex) / 2 ;
result = source[index];<br> // 如果等于0，就直接返回了，0肯定是绝对值最小的
if (result== 0 )
{
return 0 ;
}<br> // 如果值大于0，处理当前位置左侧区域，因为负数肯定在左侧
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 ;
}<br> // 如果小于0，处理当前位置右侧的区域，因为正数肯定在右侧的位置
else
{
if (index == endIndex)
break ;
if (source[index + 1 ] < 0 )
startIndex = index + 1 ;
else if (source[index + 1 ] == 0 )
return 0 ;
else
break ;
}
}
// 根据分界点计算绝对值最小的数
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);
}
}
分类: 原创 , algorithm
作者： Leo_wl
出处： http://HdhCmsTestcnblogs测试数据/Leo_wl/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
版权信息