服务器之家:专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|JavaScript|易语言|

服务器之家 - 编程语言 - Java教程 - Java实现删除排序数组中重复元素的方法小结【三种方法比较】

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

2021-07-17 11:06PayneWoo Java教程

这篇文章主要介绍了Java实现删除排序数组中重复元素的方法,结合实例形式对比分析了三种常见的数组元素删除算法操作技巧,需要的朋友可以参考下

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

题目描述:

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

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

一:通过arraylist解决

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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)

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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)

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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:本站还有两款比较简单实用的在线文本去重复工具,推荐给大家使用:

在线去除重复项工具:https://tool.zzvips.com/t/quchong/

在线文本去重复工具:https://tool.zzvips.com/t/txtquchong/

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

原文链接:https://blog.csdn.net/wu2304211/article/details/52743589

延伸 · 阅读

精彩推荐