随笔 - 312, 文章 - 14, 评论 - 1395, 引用 - 0
数据加载中……

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

    有一个已经排序的数组(升序),数组中可能有正数、负数或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)
        {
                //  计算当前的索引
            index = startIndex + (endIndex - startIndex) / 2;
            result 
= source[index];<br>                //  如果等于0,就直接返回了,0肯定是绝对值最小的
            if(result==0)
            {
                
return 0;
            }
               //  如果值大于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;
            }
            //  如果小于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);
    }
}




Android开发完全讲义(第2版)(本书版权已输出到台湾)

http://product.dangdang.com/product.aspx?product_id=22741502



Android高薪之路:Android程序员面试宝典 http://book.360buy.com/10970314.html


新浪微博:http://t.sina.com.cn/androidguy   昵称:李宁_Lining

posted on 2013-01-30 11:45 银河使者 阅读(11270) 评论(10)  编辑  收藏 所属分类: algorithm 原创 图书

评论

# re: 百度面试题:求绝对值最小的数  回复  更多评论   

这个很明显二分
2013-01-30 17:42 | cintana

# re: 百度面试题:求绝对值最小的数[未登录]  回复  更多评论   

有序列表查找显然二分啊,博主貌似对java的arrays和collections不是很熟。
private static int getMinAbsoluteValue(final int[] source) {
int index = Arrays.binarySearch(source, 0);
int insertPos = -1 - index;
return index >= 0 ? 0
: source[insertPos == source.length ? source.length - 1
: insertPos];
}
2013-01-30 23:48 | changedi

# re: 百度面试题:求绝对值最小的数[未登录]  回复  更多评论   

object FindMinimum {
def main(args: Array[String]): Unit = {
val l = List(-20, -13, -4, 6, 77, 200)
val l2 = List(-30,-20,-20,-2)
val l3 = List(1,2,3,4,5)

def cal(list: List[Int]): Int = {
import Math._
list match {
case List(a) => a
case List(a, b) => min(abs(a), abs(b))
case List(a, b, c) => min(abs(c), min(abs(a), abs(b)))
case l =>
val len = l.length / 2
val ploc = l(len)
val ppre = l(len-1)
val loc = abs(ploc)
val pre = abs(ppre)
if ((ploc > ppre) && (loc > pre)) cal(l.take(len))
else cal(l.takeRight(len))
}
}
println(cal(l))
println(cal(l2))
println(cal(l3))

}
}
2013-01-31 11:05 | harry

# re: 百度面试题:求绝对值最小的数[未登录]  回复  更多评论   

written in Scala
object FindMinimum {
def main(args: Array[String]): Unit = {
val l = List(-20, -13, -4, 6, 77, 200)
val l2 = List(-30,-20,-10,-2)
val l3 = List(1,2,3,4,5)

def cal(list: List[Int]): Int = {
import Math._
list match {
case List(a) => a
case l =>
val len = l.length / 2
val ploc = l(len)
val ppre = l(len-1)
val loc = abs(ploc)
val pre = abs(ppre)
println(loc,pre)
if ((ploc > ppre) && (loc > pre)) cal(l.take(len))
else cal(l.takeRight(len))
}
}
println(cal(l))
println(cal(l2))
println(cal(l3))
}
}
2013-01-31 11:26 | harry

# re: 百度面试题:求绝对值最小的数  回复  更多评论   

@changedi

算法还有点问题,如果数组是{-20, -13, -4, 4, 77, 200},你的算法就只能求出一个值。当index < 0时,还应该比较下插入点附近的两个值
2013-02-24 18:50 | dohkoos

# re: 百度面试题:求绝对值最小的数  回复  更多评论   

百度的面试题真够难的啊。。。。
2013-07-09 14:37 | txt小说下载

# re: 百度面试题:求绝对值最小的数  回复  更多评论   

算法啊,我算是真的搞不来这东西……
2013-12-28 15:49 | 左岸

# re: 百度面试题:求绝对值最小的数  回复  更多评论   

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

int minabs(vector<int> &a, int start, int end){
if(start+1 == end){
return a[start];
}else if(start+2 == end){
return abs(a[start]) < abs(a[start+1]) ? a[start] : a[start+1];
}else if(a[start] * a[end-1] > 0){
return abs(a[start]) < abs(a[end-1]) ? a[start] : a[end-1];
}else{
int middle = (start+end)/2;
int leftmin = minabs(a, start, middle);
int rightmin = minabs(a,middle, end);
return abs(leftmin)< abs(rightmin)?leftmin:rightmin;
}
}

int main(){
vector<int> array;
int buf = 0;
while(cin>>buf){
array.push_back(buf);
}
cout << minabs(array, 0, array.size()) << endl;
}


2014-03-11 00:00 | jiuren

# re: 百度面试题:求绝对值最小的数  回复  更多评论   

查博主的资料看到,挺有意思的,采用二分法
int getSmallestAbsolute(int[] elements, int low, int high){
if(low == high)
return elements[low];
if(elements[low] >= 0)
return elements[low];
if(elements[high] <= 0)
return elements[high];
int mid = (low + high)/2;
return Math.min(getSmallestAbsolute(elements, low, mid),
getSmallestAbsolute(elements, mid+1, high));
}
2014-06-09 18:17 | 嗯Jeffrey

# re: 百度面试题:求绝对值最小的数  回复  更多评论   

http://www.ma4.net
2014-08-30 11:16 | 微观互联网

只有注册用户登录后才能发表评论。


网站导航: