首页 > 其他分享 >使用双指针技术去除ArrayList中的重复元素

使用双指针技术去除ArrayList中的重复元素

时间:2024-11-06 14:58:01浏览次数:3  
标签:newList ArrayList 元素 list 列表 去除 指针

技术博客:使用双指针技术去除ArrayList中的重复元素

在Java编程中,处理集合数据时,去除重复元素是一个常见的需求。本文将介绍如何使用双指针技术来高效地去除 ArrayList 中的重复元素,并通过两种不同的方法进行实现。

1. 问题背景

假设我们有一个包含重复元素的 ArrayList,例如:

ArrayList<String> list = new ArrayList<>();
Collections.addAll(list, "北京", "上海", "广州", "北京", "深圳", "上海");

我们希望得到一个去重后的列表,例如:

[北京, 广州, 上海, 深圳]

2. 方法1:使用双指针技术

双指针技术是一种高效的算法,特别适用于有序列表的去重操作。以下是实现步骤:

  1. 排序:首先对列表进行排序,以便相同的元素相邻。
  2. 双指针遍历:使用两个指针,一个指向当前元素,另一个指向新列表的末尾。如果当前元素与前一个元素不同,则将其添加到新列表中。
private static ArrayList<String> fun1(ArrayList<String> list) {
    // 对列表进行排序
    list.sort((o1, o2) -> o1.compareTo(o2));

    // 使用双指针技术去除重复元素
    int newSize = removeDuplicates(list);

    ArrayList<String> newList = new ArrayList<>();

    // 将去重后的元素添加到新列表中
    for (int i = 0; i < newSize; i++) {
        newList.add(list.get(i));
    }
    return newList;
}

private static int removeDuplicates(ArrayList<String> list) {
    if (list.isEmpty())
        return 0;

    int j = 1; // 新列表的指针

    // 遍历原始列表
    for (int i = 1; i < list.size(); i++) {
        // 如果当前元素与前一个元素不同,则将其添加到新列表中
        if (!list.get(i).equals(list.get(i - 1)))
            list.set(j++, list.get(i));
    }
    return j; // 返回新列表的大小
}

3. 方法2:使用简单的包含检查

另一种方法是使用简单的包含检查来去除重复元素。遍历原始列表,如果新列表中不包含当前元素,则将其添加到新列表中。

private static ArrayList<String> fun2(ArrayList<String> list) {
    ArrayList<String> newList = new ArrayList<>();
    for (String s : list) {
        // 如果新列表中不包含当前元素,则添加到新列表中
        if (!newList.contains(s))
            newList.add(s);
    }
    return newList;
}

4. 性能比较

  • 双指针技术:时间复杂度为 O(n log n)(排序) + O(n)(遍历),空间复杂度为 O(1)
  • 包含检查:时间复杂度为 O(n^2),因为每次 contains 操作都需要线性时间。

显然,双指针技术在处理大规模数据时更为高效。

5. 总结

本文介绍了两种去除 ArrayList 中重复元素的方法:双指针技术和简单的包含检查。双指针技术在处理有序列表时表现出色,而包含检查方法则更为直观。根据实际需求选择合适的方法,可以有效提高代码的性能和可读性。

希望这篇博客对你理解和应用双指针技术有所帮助!如果你有任何问题或建议,欢迎在评论区留言。

标签:newList,ArrayList,元素,list,列表,去除,指针
From: https://www.cnblogs.com/itcq1024/p/18530233

相关文章

  • 7.《双指针篇》---⑦三数之和(中等偏难)
    题目传送门 方法一:双指针1.新建一个顺序表用来返回结果。并排序数组。2.for循环i从第一个数组元素遍历到倒数第三个数。3.如果遍历过程中有值大于0的则break; 4.定义左右指针,以及target。intleft=i+1,right=n-1;inttarget=-nums[i];5.类似两数之和。......
  • 关于我、重生到500年前凭借C语言改变世界科技vlog.15——深入理解指针(4)
    文章目录1.回调函数的介绍2.qsort使用实例2.1qsort函数介绍2.2使用qsort函数排序整型数据2.3使用qsort排序结构数据3.qsort的模拟实现希望读者们多多三连支持小编会继续更新你们的鼓励就是我前进的动力!1.回调函数的介绍回调函数就是一个通过函数指针调用的......
  • 【C/C++】野指针概念以及避免方式
    C语言中的野指针详解野指针(WildPointer)是指向未定义或非法内存位置的指针。本博客讲解野指针的概念、产生原因、危害以及如何避免野指针的问题。1.什么是野指针野指针指的是未初始化或已经失效的指针变量。这些指针指向的内存位置不再有效,可能被系统回收或被其他变量使......
  • 【重生之我要苦学C语言】深入理解指针4
    深入理解指针4字符指针变量指针指向字符变量charch='w';char*p=&ch;指针指向字符数组chararr[10]="abcdef";char*p=arr;printf("%s\n",arr);printf("%s\n",p);结果是一样的也可以写成:char*p="abcdef";//常量字符串//将字符串首字符a的地......
  • c++:智能指针
    文章目录前言一、内存泄漏1.1内存泄漏的定义1.2内存泄漏的常见原因1.3内存泄漏的危害二、智能指针的用法和模拟实现2.1RAII2.1.1RAII的工作原理2.1.2RAII的优点2.2智能指针的原理和设计思路2.3智能指针的种类和特点2.3.1std::auto_ptr2.3.2std::unique_ptr2.3......
  • C语言第11节:指针(1)
    1.内存和地址1.1内存内存是计算机系统中用于存储数据和指令的硬件设备。它可以被视为一个巨大的、有序的字节数组。基本单位:内存的基本单位是字节(byte)。每个字节由8个位(bit)组成,可以存储0到255之间的一个数值。内存模型:从程序员的角度来看,内存可以被想象成一个巨大的一......
  • C++——用指向指针的指针的方法对5个字符串排序并输出。
    没注释的源代码#include<iostream>#include<string.h>usingnamespacestd;voidsort(char**p);intmain(){  constintm=20;  char**p,*pstr[5],str[5][m];  for(inti=0;i<5;i++)    pstr[i]=str[i];  cout<<"pleaseinput5......
  • C++——用指向指针的指针的方法对n个整数排序并输出。要求将排序单独写成一个团数,整数
    没注释的源代码#include<iostream>usingnamespacestd;voidsortNumbers(int**arr,intn);intmain(){  intn;  cout<<"enterthenumberofintegers:";  cin>>n;  int**arr=newint*[n];  for(inti=0;i<n;i++)  {......
  • C++——输入一个字符串,内有数字和非数字字符,如a123x456_ 17960?302tab5876将其中连续
    没注释的源代码#include<iostream>#include<stdio.h>usingnamespacestd;intmain(){  charstr[50],*pstr;  inti,j,k,m,e10,digit,ndigit,a[10],*pa;  cout<<"pleaseinputstring:"<<endl;  gets(str);  pstr=&str[......
  • 条件语句中同时检查指针空检查和解引用,安全么
    答案是安全的。 条件语句中同时进行空指针检查和解引用,但要确保解引用发生在检查之后,并且需要注意运算符的优先级。//例如,在C++中使用逻辑与运算符if(p!=nullptr&&*p==someValue){//这里是安全的,因为p的空指针检查在前//可以安全地访问*p} 在......