隨筆-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的,呵呵  回復  更多評論
            
          主站蜘蛛池模板: 屯昌县| 房产| 嵊州市| 响水县| 遵化市| 宝山区| 罗江县| 泊头市| 陇南市| 和政县| 澄江县| 石屏县| 梁山县| 原平市| 华阴市| 宿松县| 巴彦淖尔市| 九龙坡区| 九江县| 黔西县| 夏津县| 武胜县| 哈密市| 定陶县| 三穗县| 鄂托克前旗| 江川县| 屏东市| 东宁县| 临沂市| 安阳县| 宾阳县| 嘉黎县| 屏东市| 永靖县| 新兴县| 孝昌县| 黎城县| 台东市| 隆安县| 胶南市|