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

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

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

    posts - 27,  comments - 3,  trackbacks - 0
    一個整數數列,元素取值可能是1~N(N是一個較大的正整數)中的任意一個數,相同數值不會重復出現。設計一個算法,找出數列中符合條件的數對的個數,滿足數對中兩數的和等于N+1。 復雜度最好是O(n),如果是O(n2)則不得分。

    網上大多數人的做法時間復雜度雖然能達到 O(n), 但是空間復雜度是O(N) ,題目已經指出N是一個較大的整數,所以可能不大好。
    想了一下,想了一個空間復雜度是O(m)的算法 ,其中m是輸入整數數列的長度。設輸入的整數數組是array,符合條件的數對的個數為count,初始化為0
    1. 建立hash集合S, 遍歷array的前一半元素,對于這一半元素中的任意一個元素e, 在S中插入 N+1 - e
    2. 遍歷array的后一半元素,對于每一個元素e, 如果e在S中已經存在,則count +1
    3. 遍歷結束,返回count即可

    這個算法只需遍歷一遍輸入數組,復雜度為O(n) ,只需存儲m/2個元素,復雜度為O(m) ,如果m遠小于N,這個算法還是有很大改進的。
    posted on 2011-05-19 18:48 Jeff Lee 閱讀(216) 評論(0)  編輯  收藏 所屬分類: algorithm

    <2011年5月>
    24252627282930
    1234567
    891011121314
    15161718192021
    22232425262728
    2930311234

    常用鏈接

    留言簿(1)

    隨筆分類

    隨筆檔案

    搜索

    •  

    最新評論

    閱讀排行榜

    評論排行榜

    主站蜘蛛池模板: 亚洲福利精品电影在线观看| 在线观看国产一区亚洲bd| 亚洲 国产 图片| 亚洲免费视频观看| 99久久精品毛片免费播放| 亚洲精品无码久久久久久| 亚洲黄色网址大全| 亚洲国产精品VA在线观看麻豆| 亚洲国产精品一区二区第一页免 | 中文字幕亚洲无线码a| 91情侣在线精品国产免费| 无码免费一区二区三区免费播放| 国产99久久亚洲综合精品| 亚洲а∨天堂久久精品9966| 亚洲激情视频在线观看| 狠狠色伊人亚洲综合成人| 亚洲综合区小说区激情区| 国产做床爱无遮挡免费视频| 色婷婷7777免费视频在线观看| 18pao国产成视频永久免费| 嫩草在线视频www免费观看| 91视频免费观看| eeuss影院免费92242部| 手机永久免费的AV在线电影网| 久久亚洲中文字幕无码| 色欲aⅴ亚洲情无码AV蜜桃| 亚洲GV天堂无码男同在线观看| 亚洲欧洲精品成人久久曰| 中文字幕亚洲精品无码| 亚洲日韩久久综合中文字幕| 亚洲va成无码人在线观看| 亚洲国产美女精品久久久久| 亚洲韩国在线一卡二卡| 亚洲综合亚洲国产尤物| 4480yy私人影院亚洲| 久久综合亚洲色一区二区三区 | 日本人的色道免费网站| 在线精品一卡乱码免费| 久久天天躁狠狠躁夜夜免费观看| 成年轻人网站色免费看| 免费羞羞视频网站|