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

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

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

题目描述：

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

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

一：通过ArrayList解决

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

ArrayList list = new ArrayList();

// 去掉数组中重复的元素

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相关内容感兴趣的读者可查看本站专题：《Java数组操作技巧总结》、《Java字符与字符串操作技巧总结》、《Java数学运算技巧总结》、《Java数据结构与算法教程》及《Java操作DOM节点技巧总结》

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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。