Java实现删除排序数组中重复元素的方法小结【三种方法比较】

本文实例讲述了Java实现删除排序数组中重复元素的方法。分享给大家供大家参考，具体如下：

题目描述：

给定一个排序数组，在原数组中删除重复出现的数字，使得每个元素只出现一次，并且返回新的数组的长度。

不要使用额外的数组空间，必须在原地没有额外空间的条件下完成。

一：通过ArrayList解决

时间复杂度和空间复杂度都为O(n)

ArrayList<Integer> list = new ArrayList<Integer>();
// 去掉数组中重复的元素
public int removeTheagain01(int[] array) {
   if (array == null || array.length == 0) {
     return 0;
   } else if (array.length == 1) {
     return 1;
   } else {
     int i = 0;
     int n = array.length - 1;
     while (i <= n) {
       if (i == n) {
         list.add(array[i]);
         i++;
       } else {
         int j = i + 1;
         if (array[i] == array[j]) {
           while (j <= n && array[i] == array[j]) {
             j++;
           }
         }
         list.add(array[i]);
         i = j;
       }
     }
     for (int k = 0; k < list.size(); k++) {
       array[k] = list.get(k);
     }
     return list.size();
   }
}

二：利用System.arraycopy（）函数来复制数组

时间复杂度为O(n^2)，空间复杂度为O(n)

public int removeTheagain02(int[] array) {
   if (array == null || array.length == 0) {
     return 0;
   } else if (array.length == 1) {
     return 1;
   } else {
     int end = array.length - 1;
     for (int i = 0; i <= end; i++) {
       if (i < end) {
         int j = i + 1;
         if (array[i] == array[j]) {
           while (j <= end && array[i] == array[j]) {
             j++;
           }
         }
         System.arraycopy(array, j, array, i + 1, end - j + 1);
         end -= j - i - 1;
       }
     }
     return end + 1;
   }
}

三：借助临时变量解决问题

时间复杂度O(N),空间复杂度O(1)

public int removeTheagain03(int[] array) {
   if (array == null || array.length == 0) {
     return 0;
   } else if (array.length == 1) {
     return 1;
   } else {
     int temp = array[0];
     int len = 1;
     for (int i = 1; i < array.length; i++) {
       if (temp == array[i]) {
         continue;
       } else {
         temp = array[i];
         array[len] = array[i];
         len++;
       }
     }
     return len;
   }
}

总结：

数组下标（指针）与临时变量，是解决数组相关面试题的两 * 宝**

PS：本站还有两款比较简单实用的在线文本去重复工具，推荐给大家使用：

在线去除重复项工具：
http://tools.jb51.net/code/quchong

在线文本去重复工具：
http://tools.jb51.net/aideddesign/txt_quchong

希望本文所述对大家java程序设计有所帮助。

来源：https://blog.csdn.net/wu2304211/article/details/52743589