隨筆-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的,呵呵  回復  更多評論
            
          主站蜘蛛池模板: 青田县| 菏泽市| 秦皇岛市| 阿克陶县| 岳池县| 略阳县| 金秀| 南郑县| 子长县| 卫辉市| 弋阳县| 阿鲁科尔沁旗| 十堰市| 乌兰浩特市| 连南| 通城县| 宣城市| 满城县| 塘沽区| 陇南市| 平度市| 和平区| 新泰市| 尼玛县| 大名县| 文登市| 东兴市| 莎车县| 乌海市| 慈利县| 清镇市| 湟源县| 屏东市| 罗城| 墨竹工卡县| 于田县| 且末县| 巴南区| 临澧县| 达拉特旗| 鹿泉市|