首页 > 其他分享 >数组去重:双指针法的优雅实现

数组去重:双指针法的优雅实现

时间:2024-12-10 12:43:07浏览次数:4  
标签:arr int 复杂度 优雅 Arrays 数组 指针

数组去重:双指针法的优雅实现

在日常开发中,数组去重是一个常见的需求。无论是处理用户输入、数据清洗,还是优化算法性能,去重操作都扮演着重要角色。本文将介绍一种高效的去重方法——双指针法,并结合代码示例,帮助你轻松掌握这一技巧。


1. 问题描述

给定一个包含重复元素的数组,要求删除重复项,返回一个不包含重复元素的新数组。例如:

  • 输入:[4, 3, 2, 4, 1, 3, 5, 6, 5]
  • 输出:[1, 2, 3, 4, 5, 6]

2. 思路分析

2.1 排序的重要性

在去重之前,首先对数组进行排序。排序后,相同的元素会被排列在一起,这为后续的去重操作提供了便利。

2.2 双指针法的原理

双指针法是一种高效的算法技巧,尤其适用于有序数组的操作。其核心思想如下:

  • 慢指针(i:指向当前不重复的元素。
  • 快指针(j:遍历整个数组,寻找新元素。
  • 如果 arr[j]arr[i] 相同,说明有重复,跳过 j
  • 如果 arr[j]arr[i] 不同,说明 arr[j] 是一个新元素,将其赋值给 arr[i+1],然后 i 向前移动。

通过这种方式,可以在线性时间内完成去重操作。


3. 代码实现

以下是基于双指针法的数组去重实现:

import java.util.Arrays;

public class ArrayDuplicateRemover {
    public static void main(String[] args) {
        int[] arr = {4, 3, 2, 4, 1, 3, 5, 6, 5};

        // 1. 先对数组进行排序
        Arrays.sort(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));

        // 2. 使用双指针法去重
        int[] result = removeDuplicates(arr);
        System.out.println("Array after removing duplicates: " + Arrays.toString(result));
    }

    public static int[] removeDuplicates(int[] arr) {
        if (arr == null || arr.length == 0) {
            return arr;
        }

        int i = 0; // 慢指针

        // 快指针 j 从 1 开始遍历
        for (int j = 1; j < arr.length; j++) {
            // 如果当前元素与慢指针指向的元素不同,说明是新元素
            if (arr[j] != arr[i]) {
                i++; // 慢指针向前移动
                arr[i] = arr[j]; // 将新元素赋值给慢指针的下一个位置
            }
        }

        // 返回去重后的数组(截取前 i+1 个元素)
        return Arrays.copyOf(arr, i + 1);
    }
}

4. 代码解析

4.1 排序

  • 使用 Arrays.sort(arr) 对数组进行排序。
  • 排序后,相同的元素会排列在一起,便于后续去重。

4.2 双指针法

  • 慢指针 i:初始值为 0,指向当前不重复的元素。
  • 快指针 j:从 1 开始遍历数组,寻找新元素。
  • 如果 arr[j] != arr[i],说明 arr[j] 是一个新元素,将其赋值给 arr[i+1],然后 i 向前移动。

4.3 返回结果

  • 使用 Arrays.copyOf(arr, i + 1) 截取去重后的数组。

5. 示例运行

输入

int[] arr = {4, 3, 2, 4, 1, 3, 5, 6, 5};

输出

Sorted array: [1, 2, 3, 3, 4, 4, 5, 5, 6]
Array after removing duplicates: [1, 2, 3, 4, 5, 6]

6. 复杂度分析

6.1 时间复杂度

  • 排序O(n log n)
  • 双指针遍历O(n)
  • 总时间复杂度:O(n log n)

6.2 空间复杂度

  • 只使用了常数级别的额外空间,空间复杂度为 O(1)

7. 总结

双指针法是一种非常优雅且高效的去重方法,尤其适用于有序数组。通过排序和双指针的结合,我们可以在 O(n log n) 的时间复杂度内完成去重操作,同时保持空间复杂度为 O(1)

标签:arr,int,复杂度,优雅,Arrays,数组,指针
From: https://www.cnblogs.com/itcq1024/p/18597160

相关文章

  • C语言整理第八章(指针)
    指针(二)一,字符指针变量(一)用字符指针指向字符串常量有两种方法初始化和赋值1,初始化intmain(){char*p="Doyouknow?";} 2,赋值intmain(){char*p;p="Doyouknow?";} 其实,无论是初始化还是赋值,都是将字符串的第一个字母的地址赋给指针变量(二)字......
  • 请说说JS中的索引数组、关联数组和静态数组、动态数组的定义与区别
    在JavaScript中,数组的概念比较灵活,不像一些强类型语言那样区分得那么严格。JS中的数组实际上是一种特殊的对象,既可以像索引数组一样通过数字索引访问元素,也可以像关联数组一样通过字符串键访问元素。所以,严格意义上来说,JS只有动态数组,它兼具了索引数组和关联数组的特性。而静......
  • Astro Zen Blog |一个优雅、极简、强大的博客
    介绍AstroZen博客项目如果你想部署一个自己的静态博客,又不想到处折腾,并且是熟悉的前端技术栈,你可以尝试下:AstroZenBlog!AstroZenBlog是一个使用Astro构建的极简、响应式和SEO友好的博客模板。它具有简洁的设计、暗色模式支持和基于markdown的内容管理。特性......
  • 智能指针中的share_ptr(共享智能指针)
    初始化共享智能指针是指多个智能指针可以同时管理同一块有效的内存,共享智能指针share_ptr是一个模板类,如果进行初始化有三种方式如下:通过构造函数初始化std::makeshared辅助函数reset方法共享智能指针对象初始化完毕之后就指向了要管理的那块堆区内存,如果想......
  • JS代码片段-Array数组克隆的几种方法
    JavaScript自身提供了几种克隆数组的方法,以下做了汇总,以作参考:1.展开运算符(...) ES6引入了展开运算符(...),这是创建数组浅克隆最常见的方法。leta=[1,2,3,4,5];letb=[...a];2.Array.from()leta=[1,2,3,4,5];letb=Array.from(a);3.Array.prototype.s......
  • 一道C语言指针有关问题的讲解
    原题#include<stdio.h>intmain(){char*c[]={"ENTER","NEW","POINT","FIRST"};char**cp[]={c+3,c+2,c+1,c};char***cpp=cp;printf("%s\n",**++cpp);printf(&quo......
  • 初识C语言(指针、结构体)
    *前言学习C语言自用教材:C程序设计第五版--谭浩强线上课程:跟学博主:鹏哥C语言。视频:1.【初识C语言】认识C语言_哔哩哔哩_bilibili1.指针1.1内存内存是电脑上特别重要的存储器,计算机中程序的运行都是在内存中进行的。为了有效的使用内存,把内存划分成一个个小的内存单......
  • 2.7 指针什么时候表示值什么时候表示地址
    1. 指针表示地址-声明时:当你声明一个指针变量时,这个变量本身存储的是一个地址。例如, int*p; 这里的 p 是一个指针变量,它被用来存储一个 int 类型变量的地址。-作为函数参数传递时:当你把一个指针作为函数参数传递时,你传递的是地址。例如, voidfunc(int*ptr); 这......
  • 数组中的第K个最大元素:算法实现与性能分析
    问题背景在算法面试和实际编程中,找出数组中第K大的元素是一个常见且经典的问题。本文将深入探讨该问题的两种主要解决方案:快速选择算法和堆排序方法。问题描述给定一个未排序的整数数组nums和一个整数k,要求找出数组中第k个最大的元素。注意,这里的"第k大"意味着排序......
  • 数组中的逆序对:基于归并排序的高效解法
    问题背景在算法和数据结构领域,"逆序对"是一个经典的计算问题。逆序对定义为数组中前面的元素大于后面的元素的数对。例如,在序列[7,5,6,4]中,存在的逆序对包括:(7,5)(7,6)(7,4)(5,4)(6,4)问题分析问题要求给定一个整数数组,要求计算数组中所有逆序对的总数。暴力解法的局......