一个编程题的几种算法比较

Question

class HighArray
   {
   private long[] a;                 // ref to array a
   private int nElems;               // number of data items
   //-----------------------------------------------------------
   public HighArray(int max)         // constructor
      {
      a = new long[max];                 // create the array
      nElems = 0;                        // no items yet
      }
   //-----------------------------------------------------------
   public boolean find(long searchKey)
      {                              // find specified value
      int j;
      for(j=0; j<nElems; j++)            // for each element,
         if(a[j] == searchKey)           // found item?
            break;                       // exit loop before end
      if(j == nElems)                    // gone to end?
         return false;                   // yes, can't find it
      else
         return true;                    // no, found it
      }  // end find()
   //-----------------------------------------------------------
   public void insert(long value)    // put element into array
      {
      a[nElems] = value;             // insert it
      nElems++;                      // increment size
      }
   //-----------------------------------------------------------
   public boolean delete(long value)
      {
      int j;
      for(j=0; j<nElems; j++)        // look for it
         if( value == a[j] )
            break;
      if(j==nElems)                  // can't find it
         return false;
      else                           // found it
         {
         for(int k=j; k<nElems; k++) // move higher ones down
            a[k] = a[k+1];
         nElems--;                   // decrement size
         return true;
         }
      }  // end delete()
   //-----------------------------------------------------------
   public void noDup() {   
     for(int i=0;i<nElems;i++) {
   for(int j =i+1;j<nElems;j++) {
     if(a[i]==a[j]) {
       a[j] = -1;
     }
   } 
 }
 for(int i=nElems-1; i>=0; i--) {
   if(a[i] == -1)
     delete(-1);
 }
 } 
   //-----------------------------------------------------------  
   public void display()             // displays array contents
      {
      for(int j=0; j<nElems; j++)       // for each element,
         System.out.print(a[j] + " ");  // display it
      System.out.println("");
      }
   //-----------------------------------------------------------
   }  // end class HighArray
////////////////////////////////////////////////////////////////
class HighArrayApp
   {
   public static void main(String[] args)
      {
      int maxSize = 100;            // array size
      HighArray arr;                // reference to array
      arr = new HighArray(maxSize); // create the array      arr.insert(77);               // insert 10 items
      arr.insert(77);
      arr.insert(44);
      arr.insert(55);
      arr.insert(22);
      arr.insert(88);
      arr.insert(11);
      arr.insert(00);
      arr.insert(66);
      arr.insert(33);      arr.display();                // display items      int searchKey = 35;           // search for item
      if( arr.find(searchKey) )
         System.out.println("Found " + searchKey);
      else
         System.out.println("Can't find " + searchKey);      arr.delete(00);               // delete 3 items
      arr.delete(55);
      arr.delete(99);      arr.insert(55);
      arr.insert(44);
      arr.insert(44);
      arr.insert(55);
      arr.display();
      arr.noDup();
      arr.display();               // display items again
      }  // end main()
   }  // end class HighArrayApp------------------------------------------------------------------------------------------------------------------作业要求:向highArray.java程序(清单2.3)的HighArray类中加入一个noDup()的方法,使之可以将数组中的所有重复数据项删除.即如果数组中有三个数据项的关键字为17, noDup()方法将会删除其中的两个.不必考试保持数据项的顺序.一种方法是先用每一个数据项比较,并用null（或是一个不会用在真正的关键字中的特殊值）将重复的数据项覆盖掉。然后将所有的null删除，当然还要缩小数组的大小。
下面的noDup()是我的方法：
------------------------------------------------------
public void noDup() { 
for(int i=0;i<nElems;i++) {
for(int j =i+1;j<nElems;j++) {
if(a[i]==a[j]) {
a[j] = -1;
}
} 
}
for(int i=nElems-1; i>=0; i--) {
if(a[i] == -1)
delete(-1);
}
} ---------------------------------------------------------------------还有一种是方法是这样的，麻烦大家比较下这2种方法有区别嘛，哪个比较好一些呢？
public void noDup(){       //标记部分int nCount = 0; //标记计数器。for(int i=0; i<nElems; i++)for(int j=0; j<i; j++)    if(a[j] == a[i])        {        if(a[i] != -1)  //排除特殊标记            {             a[i] = -1;  //特殊标记，假设用户不会输入负值。                 nCount++;             }        }//调整部分long[] b = new long[nElems - nCount];int nLength = 0;int nVariable = 0;//变数，根据-1值变化调整下标。for(int i=0; i<nElems; i++){if(a[i] != -1){//文字常量，通过它计算实际数组下标，数组下标从０开始。        b[nElems - nCount - 1 + nVariable - i] = a[i];
           nLength++;
}
else
       nVariable++;
}//赋值部份
nElems = nLength;
a = b;
}

Answer 1

其实你可以把数组中的数全部存到set里面去,因为set里面的元素是不能重复的,然后把它取出来放到数组中去.这样就不用判断了public static void main(String[] args) {
Set<Long> set=new HashSet<Long>();
long[] a=new long[]{1,2,1,3,5,4,2};
for(int i=0;i<a.length;i++){
set.add(a[i]);
}
Iterator<Long> it=set.iterator();
for(int i=0;i<set.size();i++){
a[i]=it.next();
System.out.println(a[i]+" ");
}
}但是我没看明白你说的改变数组大小是什么意思,是把原始的数组大小改成删除后的大小吗?

Answer 2

其实去重方法就是,先比较标记,然后就是移动
第一种方法，比较标记的时间复杂度是O(N^2)，移动的时间复杂度也是O(N^2)
第二种方法，比较标记的时间复杂度是O(N^2)，移动的时间复杂度是O(N)
所以第二种方法要好！