百度面试题:求绝对值最小的数

简介:

有一个已经排序的数组(升序),数组中可能有正数、负数或0,求数组中元素的绝对值最小的数,要求,不能用顺序比较的方法(复杂度需要小于O(n)),可以使用任何语言实现

例如,数组{-20,-13,-4, 6, 77,200} ,绝对值最小的是-4。

 

算法实现的基本思路

找到负数和正数的分界点,如果正好是0就是它了,如果是正数,再和左面相邻的负数绝对值比较,如果是负数,取取绝对值与右面正数比较。还要考虑数组只有正数或负数的情况。

我根据这个思路用Java简单实现了一个算法。大家有更好的实现方法欢迎跟帖

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
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);
     }
}

 上面的代码分别输出1、-4和1

本文转自银河使者博客园博客,原文链接http://www.cnblogs.com/nokiaguy/archive/2013/01/29/2881476.html如需转载请自行联系原作者


银河使者

相关文章
|
1月前
剑指Offer LeetCode 面试题40. 最小的k个数
剑指Offer LeetCode 面试题40. 最小的k个数
25 0
|
6天前
|
存储 算法 NoSQL
百度面试:如何用Redis实现限流?
百度面试:如何用Redis实现限流?
23 2
|
28天前
|
程序员 PHP Python
2024年Python最全Python基础教程:keys()、values()和 items()方法,百度面试题php
2024年Python最全Python基础教程:keys()、values()和 items()方法,百度面试题php
2024年Python最全Python基础教程:keys()、values()和 items()方法,百度面试题php
|
1月前
|
定位技术 API
Angular 调用导入百度地图API接口,2024春招BAT面试真题详解
Angular 调用导入百度地图API接口,2024春招BAT面试真题详解
|
1月前
|
Android开发
Flutter完整开发实战详解(六、 深入Widget原理),2024百度Android岗面试真题收录解析
Flutter完整开发实战详解(六、 深入Widget原理),2024百度Android岗面试真题收录解析
|
1月前
|
缓存 算法 自动驾驶
百度Cyber框架面试总结
百度Cyber框架面试总结
25 0
|
1月前
|
存储 缓存 安全
兄弟面试了百度,面试题分享一波
兄弟面试了百度,面试题分享一波
48 0
|
1月前
|
NoSQL Java 中间件
百度面试,跪了!凉经分享
百度面试,跪了!凉经分享
49 0
|
1月前
|
存储 前端开发 JavaScript
【面试题】(简单粗暴点)百度一面,直接问痛我
【面试题】(简单粗暴点)百度一面,直接问痛我
|
1月前
|
机器学习/深度学习 自然语言处理 算法
百度2024校招机器学习、数据挖掘、自然语言处理方向面试经历
百度2024校招机器学习、数据挖掘、自然语言处理方向面试经历
165 2