隨筆-28  評論-51  文章-10  trackbacks-0

          面試的常考題,關注算法復雜度和空間,

          假如是下面的方法判斷是否有重復
          int a[MAX] = {0};
          unsigned int x;
          for(int i=0;i <n;i++)
          {
             //讀入x
             if(a[x]==1)
             {
                 //x重復出現(xiàn)了
             }
             else
             {
                 a[x]=1;
             }
          }

          那么,MAX比較大時就不合適了
          但是可以把“用int數(shù)組記錄是否重復”改為“用每一個bit記錄是否重復”,于是變成:
          int a[MAX] = {0};
          unsigned int x;
          const int iBitCount = 32;
          for(int i=0;i <n;i++)
          {
             //讀入x
             if(a[x/iBitCount]& (1 < <(x%iBitCount))!=0)
             {
                 //x重復出現(xiàn)了
             }
             else
             {
                 a[x/iBitCount] ¦= (1 < <(x%iBitCount));
             }
          }

          另有,原地排序等O(1),排序后除重等


          posted on 2008-04-22 22:47 fullfocus 閱讀(851) 評論(2)  編輯  收藏 所屬分類: 算法

          評論:
          # re: (轉(zhuǎn))判斷數(shù)組中元素是否重復 2008-04-23 16:25 | 初學者
          你為什么不用list自帶的方法去判斷呢?  回復  更多評論
            
          # re: (轉(zhuǎn))判斷數(shù)組中元素是否重復[未登錄] 2008-04-23 18:25 | fullfocus
          同學,這個是面試題啊,如果沒有自己的邏輯,用現(xiàn)成的會被BS的,呵呵  回復  更多評論
            
          主站蜘蛛池模板: 高台县| 新民市| 三河市| 平和县| 庄河市| 长子县| 洞头县| 尼玛县| 皮山县| 彭阳县| 鄂伦春自治旗| 固原市| 澄迈县| 玛沁县| 永登县| 阿拉善盟| 安吉县| 嘉峪关市| 碌曲县| 夹江县| 灌南县| 和静县| 苍南县| 丹棱县| 祁连县| 甘洛县| 揭西县| 太仓市| 武陟县| 黔西| 天峻县| 伊宁县| 汝城县| 万安县| 阿尔山市| 商丘市| 当阳市| 巴楚县| 南部县| 泸水县| 武陟县|