有序数组去掉重复数据项，求良方..

一个有序的数组中删除掉重复的数据项而不破坏其有序性。一种方法是没发现一个重复的数据项，就从这个位置开始到数组结尾都向前移动一个位置，但是这就导致消耗很长的O(n^2)的时间级。要求设计算法，不论有多少重复数据，要确保数据项最多只能移动一次。这样算法就只消耗O(n)数量级额时间。

解决方案 »

  1.   

    以什么为key和value呢？还能保证有序性吗？
    倒是可以用List就是不晓得复杂度怎么算...
      

  2.   

    要求写算法啊.如果没这要求,倒可以把数据放Set里,再把数据放回数组里.
      

  3.   

    声明一个ArrayList，然后遍历你的有序数组，
    遍历时以if(list[i] == arraylist.get(arraylist.size()))为条件
    如果满足就说明重复，跳过当前遍历
    否则就将这个元素加到ArrayList里
    另外注意第一次遍历的数组越界问题
      

  4.   

    其实...在java里这个算法基本没有太多的效率问题
    java并不直接复制对象,除非是object clone操作
    除此以外都是复制引用所以,既然不存在对象复制到问题,算法时间消耗也无需太多考虑了