一个简单的思路,就是一次性遍历数组,求出数组的元素的绝对值的最小值,这样的时间复杂度为O(n)。但是,这样就浪费了题目的一个条件:数组是已经排好序的。所以,需要对原来的题目进行转换。考虑到数组有序,则元素绝对值的最小值为数组中最大负数的绝对值与最小非负数的绝对值的最小值。于是,题目事实上是去查找原数组中负数集合中的最大值。(为什么就不是非负数集合中的最小值呢?怎么判断出来一定是负数的?)
二分查找啊。中间的数如果是正数,就往前找,反之往后找。O(logn)
“题目事实上是去查找原数组中负数集合中的最大值”,因为找到这个最大复数,右边的数自然是最小正数啦
“题目事实上是去查找原数组中负数集合中的最大值”,因为找到这个最大复数,右边的数自然是最小正数啦
温馨提示:答案为网友推荐,仅供参考
第1个回答 2013-11-21
负数最大,整数最小才对啊。
倒着来也一样。得从中间来。用2分法就可以了。追问
倒着来也一样。得从中间来。用2分法就可以了。追问
对啊,但是这里却说只要负数的最大,那正数的最小怎么就不要了呢?
追答莫较真。。。
第2个回答 2013-11-21
首尾两个做标准条件left,right.找个基准值(建议选中间值)p。类似快速排序 不过只拍一次就好了 最后(p == left && p == right)