有一个已经排序的数组（升序），数组中可能有正数、负数或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如需转载请自行联系原作者
银河使者
