这个算法很让我头疼

Question

3.3在insertSort.java程序（清单3.3）中增加一个名为noDups()的方法，这个方法从已经有 
 * 序的数组中删掉重复的数据项而不破坏有序性。（可以用insertionSort()方法对数据排序， 
 * 或者也可以简单地用main()方法将数据有序地插入到表中。）一种解决方法是每发现一个重复 
 * 的数据，就从这个位置开始到数组结尾都向前移动一个位置，但这样就导致消耗很长的O(N2)的 
 * 时间级，起码在有很多重复数据项的情况下是这样的。在设计的算法中，不论有多少重复数据， 
 * 要确保数据项最多只能移动一次。这样算法只消耗O(N)数量级的时间。 * 就目前来讲我暂时还想不出在不开辟新的空间，来达到书中作业要求的“要确保 
 * 数据项最多只能移动一次”这个目标。希望查看此源码的大侠们能给出好的方法。class ArrayIns
   {
   private long[] a;                 // ref to array a
   private int nElems;               // number of data items
//--------------------------------------------------------------
   public ArrayIns(int max)          // constructor
      {
      a = new long[max];                 // create the array
      nElems = 0;                        // no items yet
      }
//--------------------------------------------------------------
   public void insert(long value)    // put element into array
      {
      a[nElems] = value;             // insert it
      nElems++;                      // increment size
      }
//--------------------------------------------------------------
   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("");
      }
//--------------------------------------------------------------
   public void insertionSort()
      {
      int in, out;      for(out=1; out<nElems; out++)     // out is dividing line
         {
         long temp = a[out];            // remove ed item
         in = out;                      // start shifts at out
         while(in>0 && a[in-1] >= temp) // until one is smaller,
            {
            a[in] = a[in-1];            // shift item to right
            --in;                       // go left one position
            }
         a[in] = temp;                  // insert ed item
         }  // end for
      }  // end insertionSort()
//--------------------------------------------------------------
   }  // end class ArrayIns
////////////////////////////////////////////////////////////////
class InsertSortApp
   {
   public static void main(String[] args)
      {
      int maxSize = 100;            // array size
      ArrayIns arr;                 // reference to array
      arr = new ArrayIns(maxSize);  // create the array      arr.insert(77);               // insert 10 items
      arr.insert(99);
      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      arr.insertionSort();          // insertion-sort them      arr.display();                // display them again
      }  // end main()
   }  // end class InsertSortApp

Answer 1

理论上数组或矩阵是不可能做到你说的要求的如果Btree或链表是完全可以的!所以我建议你还是要多看看数据结构方面的书!

Answer 2

public void noDups() {
     int i,j,nCount;
     nCount=0;
     
     for(i=0;i<nElems;i++) {
   for(j =i+1;j<nElems;j++) {
     if(a[i]==a[j]) 
       a[j] = -1;
   }
 } 
     
     for(i=0; i<nElems; i++) {
       if(a[i]==-1)
         nCount++;
       else  
         a[i-nCount]=a[i];
     }         
     nElems=nElems-nCount;
   }已经写好了，感谢楼上各位，特别是6，7，10楼的
给出宝贵意见