首页 > 其他分享 >双指针

双指针

时间:2023-04-07 13:22:05浏览次数:24  
标签:arr right 算法 数组 指针 left

前提:
双指针算法去重有一个前提,那就是数组已经是有序的状态。若数组并非有序,可以在使用本次算法之前先使用排序算法将数组转换成有序数组。本次算法为原地算法即额外空间复杂度为O(1)。本文将使用整数型数组arr作演示,其中arr的元素为0,0,1,2,2,3,5。

算法讲解:
首先我们设置一个记录要被替换位置的指针left,再设置一个游走指针right。

让right指针遍历整个数组,当right指针到达数组最后一个数字时为算法结束的标志。每一次遍历时判断left指针所指元素的值与right所指是否相等。相等代表数组存在相等的数,这时考虑到right后一位的值可能也与left值相等,即arr[left]=arr[right]=arr[right+1] 的情况,因此需要继续后移right指针,直到right所指值与left不同。

 

当right所指值与left不同时意味着left指针所指值重复结束。这时保留left的位置,将left后移一位后将right的值赋值给left,同时将right后移一位。

 

重复该操作知道right指针抵达数组的最后一个元素,在数组前left位置可以得到该数组的有序无重复数组。如本文的例子完成算法后结果为: 0, 1, 2, 3, 5, 3, 5,此时的left为4。

算法代码:
public int removeDuplicates(int[] arr) {
int left = 0; //左边指针
int right = 1; //右边指针
while (right < arr.length) {
// 当左指针所指值与右指针所指值相等时,右指针后移
if (arr[left] == arr[right]) {
right++;
} else {
/*当左指针所指与右指针不同时,左指针后移后将右指针所指值赋值给左指针,
再将右指针右移一位*/
arr[++left] = arr[right++];
}
}
return left + 1;
}

在方法的最后我返回了一个值left+1,即数组中不重复的数。
————————————————

标签:arr,right,算法,数组,指针,left
From: https://www.cnblogs.com/xvjiawei-666/p/17295840.html

相关文章

  • C#调用C++ 平台调用P/Invoke 函数指针/回调函数【二】
    Gitp-invoke源码地址 C#调用C++平台调用P/Invoke调用约定【一】C#调用C++平台调用P/Invoke函数指针/回调函数【二】C#调用C++平台调用P/Invoke字符串【三】C#调用C++平台调用P/Invoke错误码LastError【四】C#调用C++平台调用P/Invoke结构体--输入输出参数、返回值、返......
  • C++逆向分析——this指针
    this指针概述C++是对C的拓展,C原有的语法C++都支持,并在此基础上拓展了一些语法:封装、继承、多态、模板等等。C++拓展新的语法是为了让使用更加方便、高效,这样就需要编译器多做了很多事情,接下来我们就需要一一学习这些概念。封装之前我们学习过结构体这个概念,那么结构体可以......
  • 单链表进阶OJ版--->随机指针问题
    朋友们,晚上好!!今天,推出一篇单链表的随机指针问题!!相较于之前的链表OJ题,本期的链表难度有所提升!!下面请看题:>有一个链表,链表每个结点额外增加一个随机指针random,并且随机指针可以指向链表的任何结点以及空结点至于本题的要求是:复制带随机指针的链表如下图所示:>本题的难度,大致......
  • Auto Chess (双指针, 极角排序)
    题目大意:释放一个45都的技能去尽可能消灭更多的敌人(在一个平面里面)  思路:技能是无线长的,于是抛弃无用信息,只保留斜率即可然后利用双指针,或者二分去做即可 ......
  • 指针和引用的区别
    指针和引用在C++中都用于间接访问变量,但它们有一些区别:指针是一个变量,它保存了另一个变量的内存地址,引用是另一个变量的别名,与原变量共享内存地址。指针可以被重新赋值,指向不同的变量,引用在初始化后不能更改,始终指向同一个变量。指针可以为nullptr,表示不指向任何变量;引用......
  • C语言——复杂指针的读写
     1int*(*(*(*abc)())[6])();2/*3*1、(*abc)()——函数指针4*2、(*(某1))[6]——某的数组的指针5*3、int*(*(某2))()——返回值为int*类型的某的函数指针6*组合方式:123217*组合:(以(指向((返回值为int*类型的(函数指针))数组)的指针)......
  • 对于数组和指针的关系的测试
    #include"stdio.h"//验证数组和指针的以下一些关系//1.一元数组名本质上是数组第一个元素的地址,也是数组的地址//2。数组中存在a[2]=*(a+2)//3.数组在传递的时候传递的是数组名,也就是传递的是它的地址intmain(){intc[3]={1,2,3};int*a=c;//此时的a表示c数组......
  • [rust学习] 二、 rust中的智能指针
     rust中智能指针大致分类以下内容提炼自rust官方文档: https://doc.rust-lang.org/book/ch15-01-box.html 一、Box<T>1.使用例子:  1fnmain(){2letb=Box::new(5);3println!("b={}",b);4}2.特性:a.由B......
  • 138. 复制带随机指针的链表
    /*//DefinitionforaNode.classNode{public:intval;Node*next;Node*random;Node(int_val){val=_val;next=NULL;random=NULL;}};*/classSolution{public:Node*copyRandomList(Node*......
  • 快慢指针-leetcode27移除元素
    给你一个数组nums和一个值val,你需要原地移除所有数值等于val的元素,并返回移除后数组的新长度。不要使用额外的数组空间,你必须仅使用O(1)额外空间并原地修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。说明:为什么返回数值是整数,但输......