愚僧

赢与输的差别通常是--不放弃

BlogJava 首页 新随笔 联系 聚合 管理
  23 Posts :: 0 Stories :: 2 Comments :: 0 Trackbacks

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

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


package web;

import java.util.Arrays;

/**
 * 有一个已经排序的数组(升序), 数组中可能有正数、负数或0,求数组中元素的绝对值最小的数, 要求,不能用顺序比较的方法 求绝对值最小的数
 * 
 * 
@author mayw
 
*/
public class FindMinValue {

    /**
     * 
     * 
@param source
     *            原数组
     * 
@return 绝对值最小的数
     * 
@throws Exception 
     
*/
    public static int[] getMinAbsoluteValue(final int[] source) throws Exception {
        int[] rvs = null;
        if(source==null){
            throw new Exception("非法的原数组, 对象为null");
        }
        int index = binarySearch(source,0);
        int insertPos = -1 - index;
        if(index >= 0){
            return new int[]{0}; // 存在0, 0绝对值最小 
        }else if(source.length==1){
            return new int[]{source[0]};
        }else if(insertPos == source.length){
            return new int[]{source[source.length - 1]};
        }else if(insertPos == 0){
            return new int[]{source[0]};
        }else if(Math.abs(source[insertPos]) > Math.abs(source[insertPos - 1])){
            return new int[]{source[insertPos - 1]};
        }else if(Math.abs(source[insertPos]) == Math.abs(source[insertPos - 1])){
            return new int[]{source[insertPos - 1],source[insertPos],};
        }else{
            return new int[]{source[insertPos]};
        }
//        int rv = index >= 0 ? 0
//                : source[insertPos == source.length ? source.length - 1
//                        : insertPos];
//        if(){
//            
//        }
//        return index >= 0 ? 0
//                : source[insertPos == source.length ? source.length - 1
//                : insertPos];
    }

    /**
     * 使用二分搜索法来搜索指定的 int 型数组,以获得指定的值。
     * 
     * 
@param source
     *            要查找的目标数组
     * 
@param target
     *            要查找的数
     * 
@return 如果它包含在数组中,则返回搜索键的索引; 否则返回 (-(插入点) - 1)。 插入点
     *         被定义为将键插入数组的那一点:即第一个大于此键的元素索引, 如果数组中的所有元素都小于指定的键,则为 a.length。
     *         注意,这保证了当且仅当此键被找到时,返回的值将 >= 0。
     
*/
    public static int binarySearch(final int[] source, int target) {
        int low = 0;
        int high = source.length - 1;
        while(low<=high){
            int midIdx = (low+high)>>1; // 去中间索引
            int midVal = source[midIdx]; // 去中间值
            if(target < midVal){
                high = midIdx - 1; // 去中间索引的前半部分, 不包含中间索引
            }else if(target > midVal){
                low = midIdx + 1; // 去中间索引的后半部分, 不包含中间索引
            }else{
                return midIdx; // 返回当前索引
            }
        }
        return -low-1;
    }

    public static void main(String[] args) throws Exception {
        System.out.println(Arrays.toString(getMinAbsoluteValue(new int[]{0})));
        System.out.println(Arrays.toString(getMinAbsoluteValue(new int[]{-1})));
        System.out.println(Arrays.toString(getMinAbsoluteValue(new int[]{1})));
        System.out.println(Arrays.toString(getMinAbsoluteValue(new int[]{-4,-2,-1})));
        System.out.println(Arrays.toString(getMinAbsoluteValue(new int[]{-4,-2,-1,1,2,3,4})));
        System.out.println(Arrays.toString(getMinAbsoluteValue(new int[]{-4,-2,-1,2,3,4})));
        System.out.println(Arrays.toString(getMinAbsoluteValue(new int[]{-4,-2,-2,1,3,4})));
        System.out.println(Arrays.toString(getMinAbsoluteValue(new int[]{1,2,3,4})));
    }

}


from : http://www.cnblogs.com/nokiaguy/archive/2013/01/29/2881476.html
posted on 2013-02-24 20:51 ywm 阅读(168) 评论(0)  编辑  收藏 所属分类: j2se

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


网站导航: