C语言双指针算法

时间:2022-05-23 乔乔家的龙龙人气:0

双指针

首先咱得知道何为双指针，听起来很上流，其实有手就行。

双指针，指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同方向（快慢指针）或者相反方向（对撞指针）的指针进行扫描，从而达到相应的目的。

换言之，双指针法充分使用了数组有序这一特征，当遇到有序数组时，应该优先想到双指针来解决问题，因两个指针的同时遍历会减少空间复杂度和时间复杂度从而在某些情况下能够简化运算

在这里插入图片描述

对撞指针

类似于相遇问题，对撞指针是指在有序数组中，将指向最左侧的索引定义为左指针，最右侧的定义为右指针，然后分别从两侧出发，相向遍历链表，这个过程就形象化为对撞，习惯上就将左右指针定义为 left 和 right，我们给出一个大致代码逻辑：

void hit(int *arr,int arrsize)
{
int* left = arr;
int* right = arr + arrsize -1;
while(left<=right)
{
条件语句;
left++;
条件语句;
right--;
}
}

对撞指针适用于二分查找，链表对象求和等，也就是说当你遇到题目给定有序数组时，应该第一时间想到的思路就是使用对撞指针。

快慢指针

类似于龟兔赛跑，快慢指针是两个链表上的指针从同一节点出发，其中一个指针前进速度比另一个快，两个指针以不同的策略移动，直到两个指针的值达成某个条件为止，如图（ppt绘图+手残勿喷）：

在这里插入图片描述

我们同样将左右指针定义为 slow，fast，要实现其中一个指针比另一个快，我们无可厚非就两种方法：

1.同时起步，fast 比 slow 多走n步；

2.fast 先走，slow后走；

那我们给出他的逻辑代码：
同时走：

void speed(int *arr)
{
   int* fast = arr;
   int* slow = arr;
   while(slow<fast)
   {
   条件;
   slow++(非条件下fast++);
   }
}

先后走：

void speed(int *arr)
{
int* slow =arr;
int* fast = arr;
while(条件1)
{
slow++;
}
while(条件2)
{
fast++;
}
}

真题实战

1.调整数组顺序使奇数位于偶数前面

int* reOrderArray(int* array, int arrayLen, int* returnSize ) {
  *returnSize = arrayLen;
   int* left = array;
	int* right = array + arrayLen - 1;
	while (left < right)//(1)
	{
		while (left < right && *left % 2 == 1)//(2)
			left++;
		while (left < right && *right % 2 == 0)//(3)
			right--;
		if (left < right)//(4)
		{
			int tmp = *left;
			*left = *right;
			*right = tmp;
		}
		left++;
		right--;
	}
	return array;
}

这道题就是典型的对撞指针，我们遍历完整个数组时，左右指针路程各自一半，只需要 left 寻找奇数，right 寻找偶数做交换即可。

==Ps.==这里的* returnSize

2.Leetcode 真题：移除元素

int removeElement(int* nums, int numsSize, int val) {
	int* p1 = nums;
	int* p2 = nums;
	int sz = numsSize;
	for (; p1 < nums + numsSize; p1++)
	{
		if (*p1 != val)
		{
			*p2 = *p1;
			*p2++;
		}
		else
			sz--;
	}
	return sz;
}

这是典型的快慢指针，第一个指针用来遍历数组元素，判断是不是要删除的数，第二个指针用来存放数字。如果第一个指针指向的是要删除的元素，那么输出用来存放输出数组元素个数的整形变量sz就自减 1，然后第一个指针向后移动一位，第二个指针不动；如果第一个指针指向的不是要删除的数，那么就把这个数放到第二个指针指向的位置，然后第一个指针和第二个指针都向后移动一位。重复操作直到第一个指针遍历整个数组，此方法的时间复杂度是O(n)。

今天就到这里了，摸了家人们，情人节快乐！更多关于C语言双指针算法的资料请关注其它相关文章！

加载全部内容