百度面試題：求絕對值最小的數

有一個已經排序的數組（升序），數組中可能有正數、負數或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

<code>public</code> <code>class</code> <code>MinAbsoluteValue</code>

<code>{</code>

<code>    </code><code>private</code> <code>static</code> <code>int</code> <code>getMinAbsoluteValue(</code><code>int</code><code>[] source)</code>

<code>    </code><code>{</code>

<code>        </code> 

<code>        </code><code>int</code> <code>index = </code><code>0</code><code>;</code>

<code>        </code><code>int</code> <code>result = </code><code>0</code><code>; </code>

<code>        </code><code>int</code> <code>startIndex = </code><code>0</code><code>;</code>

<code>        </code><code>int</code> <code>endIndex = source.length - </code><code>1</code><code>;</code>

<code>        </code><code>//  計算負數和正數分界點</code>

<code>        </code><code>while</code><code>(</code><code>true</code><code>)</code>

<code>        </code><code>{&lt;br&gt;                </code><code>//  計算目前的索引</code>

<code>            </code><code>index = startIndex + (endIndex - startIndex) / </code><code>2</code><code>;</code>

<code>            </code><code>result = source[index];&lt;br&gt;                </code><code>//  如果等于0，就直接傳回了，0肯定是絕對值最小的</code>

<code>            </code><code>if</code><code>(result==</code><code>0</code><code>)</code>

<code>            </code><code>{</code>

<code>                </code><code>return</code> <code>0</code><code>;</code>

<code>            </code><code>}&lt;br&gt;                </code><code>//  如果值大于0，處理目前位置左側區域，因為負數肯定在左側</code>

<code>            </code><code>else</code> <code>if</code><code>(result &gt; </code><code>0</code><code>)</code>

<code>                </code><code>if</code><code>(index == </code><code>0</code><code>)</code>

<code>                </code><code>{</code>

<code>                    </code><code>break</code><code>;</code>

<code>                </code><code>}</code>

<code>                </code><code>if</code><code>(source[index-</code><code>1</code><code>] &gt;</code><code>0</code><code>)</code>

<code>                    </code><code>endIndex = index - </code><code>1</code><code>;</code>

<code>                </code><code>else</code> <code>if</code><code>(source[index-</code><code>1</code><code>] ==</code><code>0</code><code>)</code>

<code>                    </code><code>return</code> <code>0</code><code>;</code>

<code>                </code><code>else</code>

<code>            </code><code>}&lt;br&gt;                </code><code>//  如果小于0，處理目前位置右側的區域，因為正數肯定在右側的位置</code>

<code>            </code><code>else</code>

<code>                </code><code>if</code><code>(index == endIndex)</code>

<code>                </code><code>if</code><code>(source[index + </code><code>1</code><code>] &lt; </code><code>0</code><code>)</code>

<code>                    </code><code>startIndex = index + </code><code>1</code><code>;</code>

<code>                </code><code>else</code> <code>if</code><code>(source[index + </code><code>1</code><code>] == </code><code>0</code><code>)</code>

<code>            </code><code>}</code>

<code>        </code><code>}</code>

<code>        </code><code>//  根據分界點計算絕對值最小的數</code>

<code>        </code><code>if</code><code>(source[index] &gt; </code><code>0</code><code>)</code>

<code>        </code><code>{</code>

<code>            </code><code>if</code><code>(index == </code><code>0</code> <code>|| source[index] &lt; Math.abs(source[index-</code><code>1</code><code>]))</code>

<code>                </code><code>result= source[index];</code>

<code>                </code><code>result = source[index-</code><code>1</code><code>];</code>

<code>        </code><code>else</code>

<code>            </code><code>if</code><code>(index == source.length - </code><code>1</code> <code>|| Math.abs(source[index]) &lt; source[index+</code><code>1</code><code>])</code>

<code>                </code><code>result = source[index+</code><code>1</code><code>];</code>

<code>        </code><code>return</code> <code>result;</code>

<code>    </code><code>}</code>

<code>    </code><code>public</code> <code>static</code> <code>void</code> <code>main(String[] args) </code><code>throws</code> <code>Exception</code>

<code>        </code><code>int</code><code>[] arr1 = </code><code>new</code> <code>int</code><code>[]{-</code><code>23</code><code>,-</code><code>22</code><code>,-</code><code>3</code><code>,-</code><code>2</code><code>,</code><code>1</code><code>,</code><code>2</code><code>,</code><code>3</code><code>,</code><code>5</code><code>,</code><code>20</code><code>,</code><code>120</code><code>};</code>

<code>        </code><code>int</code><code>[] arr2 = </code><code>new</code> <code>int</code><code>[]{-</code><code>23</code><code>,-</code><code>22</code><code>,-</code><code>12</code><code>,-</code><code>6</code><code>,-</code><code>4</code><code>};</code>

<code>        </code><code>int</code><code>[] arr3 = </code><code>new</code> <code>int</code><code>[]{</code><code>1</code><code>,</code><code>22</code><code>,</code><code>33</code><code>,</code><code>55</code><code>,</code><code>66</code><code>,</code><code>333</code><code>};</code>

<code>        </code><code>int</code> <code>value = getMinAbsoluteValue(arr1);</code>

<code>        </code><code>System.out.println(value);</code>

<code>        </code><code>value = getMinAbsoluteValue(arr2);</code>

<code>        </code><code>value = getMinAbsoluteValue(arr3);</code>

<code>}</code>

 上面的代碼分别輸出1、-4和1

本文轉自銀河使者部落格園部落格，原文連結http://www.cnblogs.com/nokiaguy/archive/2013/01/29/2881476.html如需轉載請自行聯系原作者

銀河使者