<rt id="bn8ez"></rt>
<label id="bn8ez"></label>

  • <span id="bn8ez"></span>

    <label id="bn8ez"><meter id="bn8ez"></meter></label>

    愚僧

    贏與輸?shù)牟顒e通常是--不放棄

    BlogJava 首頁(yè) 新隨筆 聯(lián)系 聚合 管理
      23 Posts :: 0 Stories :: 2 Comments :: 0 Trackbacks

    有一個(gè)已經(jīng)排序的數(shù)組(升序),數(shù)組中可能有正數(shù)、負(fù)數(shù)或0,求數(shù)組中元素的絕對(duì)值最小的數(shù),要求,不能用順序比較的方法(復(fù)雜度需要小于O(n)),可以使用任何語(yǔ)言實(shí)現(xiàn)

    例如,數(shù)組{-20,-13,-4, 6, 77,200} ,絕對(duì)值最小的是-4。


    package web;

    import java.util.Arrays;

    /**
     * 有一個(gè)已經(jīng)排序的數(shù)組(升序), 數(shù)組中可能有正數(shù)、負(fù)數(shù)或0,求數(shù)組中元素的絕對(duì)值最小的數(shù), 要求,不能用順序比較的方法 求絕對(duì)值最小的數(shù)
     * 
     * 
    @author mayw
     
    */
    public class FindMinValue {

        /**
         * 
         * 
    @param source
         *            原數(shù)組
         * 
    @return 絕對(duì)值最小的數(shù)
         * 
    @throws Exception 
         
    */
        public static int[] getMinAbsoluteValue(final int[] source) throws Exception {
            int[] rvs = null;
            if(source==null){
                throw new Exception("非法的原數(shù)組, 對(duì)象為null");
            }
            int index = binarySearch(source,0);
            int insertPos = -1 - index;
            if(index >= 0){
                return new int[]{0}; // 存在0, 0絕對(duì)值最小 
            }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];
        }

        /**
         * 使用二分搜索法來(lái)搜索指定的 int 型數(shù)組,以獲得指定的值。
         * 
         * 
    @param source
         *            要查找的目標(biāo)數(shù)組
         * 
    @param target
         *            要查找的數(shù)
         * 
    @return 如果它包含在數(shù)組中,則返回搜索鍵的索引; 否則返回 (-(插入點(diǎn)) - 1)。 插入點(diǎn)
         *         被定義為將鍵插入數(shù)組的那一點(diǎn):即第一個(gè)大于此鍵的元素索引, 如果數(shù)組中的所有元素都小于指定的鍵,則為 a.length。
         *         注意,這保證了當(dāng)且僅當(dāng)此鍵被找到時(shí),返回的值將 >= 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; // 返回當(dāng)前索引
                }
            }
            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 閱讀(182) 評(píng)論(0)  編輯  收藏 所屬分類: j2se

    只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。


    網(wǎng)站導(dǎo)航:
     
    主站蜘蛛池模板: 国产免费观看黄AV片| 日本一区二区三区免费高清在线| 男男gay做爽爽的视频免费| 无码乱肉视频免费大全合集| 亚洲AV无码精品色午夜在线观看| 一级毛片免费在线播放| 亚洲av手机在线观看| 亚洲香蕉免费有线视频| 一个人免费视频观看在线www| 亚洲午夜福利AV一区二区无码| 成人亚洲综合天堂| 亚洲人成7777影视在线观看| 亚欧国产一级在线免费| 亚洲成?Ⅴ人在线观看无码| 中文字幕无码免费久久| 亚洲黄色网址在线观看| 国产又黄又爽又刺激的免费网址| 国产精品亚洲а∨无码播放不卡 | 亚洲人成网站在线播放影院在线 | 亚洲色欲色欱wwW在线| 日韩成人免费在线| 久久水蜜桃亚洲AV无码精品| 又粗又硬又大又爽免费视频播放| 色爽黄1000部免费软件下载| 国产亚洲一区二区在线观看| 最近中文字幕mv免费高清视频8| 亚洲毛片在线免费观看| 成人激情免费视频| 日韩在线一区二区三区免费视频| 亚洲免费视频网址| 亚洲中文字幕无码中文字在线| 久久免费福利视频| 亚洲日本乱码卡2卡3卡新区| 亚洲av无码国产精品色在线看不卡| 91热久久免费精品99| 2022国内精品免费福利视频| 久久亚洲中文无码咪咪爱| 亚洲区视频在线观看| 久久亚洲精品无码AV红樱桃| 好男人视频社区精品免费| 国产黄在线观看免费观看不卡|