隨筆-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重復出現了
             }
             else
             {
                 a[x]=1;
             }
          }

          那么,MAX比較大時就不合適了
          但是可以把“用int數組記錄是否重復”改為“用每一個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重復出現了
             }
             else
             {
                 a[x/iBitCount] ¦= (1 < <(x%iBitCount));
             }
          }

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


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

          評論:
          # re: (轉)判斷數組中元素是否重復 2008-04-23 16:25 | 初學者
          你為什么不用list自帶的方法去判斷呢?  回復  更多評論
            
          # re: (轉)判斷數組中元素是否重復[未登錄] 2008-04-23 18:25 | fullfocus
          同學,這個是面試題啊,如果沒有自己的邏輯,用現成的會被BS的,呵呵  回復  更多評論
            
          主站蜘蛛池模板: 临潭县| 灯塔市| 广州市| 凤台县| 清流县| 平武县| 巴塘县| 临桂县| 晋江市| 呼和浩特市| 娄底市| 临江市| 泸州市| 海门市| 修文县| 泰兴市| 东城区| 抚州市| 垣曲县| 茌平县| 玛曲县| 曲沃县| 宜城市| 大关县| 固原市| 齐齐哈尔市| 南木林县| 黑山县| 漠河县| 襄樊市| 红安县| 泰和县| 新建县| 莆田市| 来安县| SHOW| 旬阳县| 绵阳市| 南京市| 和林格尔县| 乌兰浩特市|