iis服务器助手广告广告
返回顶部
首页 > 资讯 > 后端开发 > 其他教程 >C语言双指针算法朋友过情人节我过算法
  • 350
分享到

C语言双指针算法朋友过情人节我过算法

2024-04-02 19:04:59 350人浏览 安东尼
摘要

目录双指针对撞指针快慢指针真题实战双指针 首先咱得知道何为双指针,听起来很上流,其实有手就行。 双指针,指的是在遍历对象的过程中,不是普通的使用单个指针进行访问,而是使用两个相同方向

双指针

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

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

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

在这里插入图片描述

对撞指针

类似于相遇问题,对撞指针是指在有序数组中,将指向最左侧的索引定义为左指针,最右侧的定义为右指针,然后分别从两侧出发,相向遍历链表,这个过程就形象化为对撞,习惯上就将左右指针定义为 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语言双指针算法的资料请关注编程网其它相关文章!

--结束END--

本文标题: C语言双指针算法朋友过情人节我过算法

本文链接: https://www.lsjlt.com/news/139099.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com    QQ/279061341

本篇文章演示代码以及资料文档资料下载

下载Word文档到电脑,方便收藏和打印~

下载Word文档
猜你喜欢
  • C语言双指针算法朋友过情人节我过算法
    目录双指针对撞指针快慢指针真题实战双指针 首先咱得知道何为双指针,听起来很上流,其实有手就行。 双指针,指的是在遍历对象的过程中,不是普通的使用单个指针进行访问,而是使用两个相同方向...
    99+
    2024-04-02
  • C语言双指针算法怎么用
    这篇“C语言双指针算法怎么用”文章的知识点大部分人都不太理解,所以小编给大家总结了以下内容,内容详细,步骤清晰,具有一定的借鉴价值,希望大家阅读完这篇文章能有所收获,下面我们一起来看看这篇“C语言双指针算法怎么用”文章吧。双指针首先咱得知道...
    99+
    2023-06-29
  • C语言 八大排序算法的过程图解及实现代码
    目录前言一、插入排序时间复杂度空间复杂度代码实现(升序)二、希尔排序时间复杂度空间复杂度代码实现三、选择排序时间复杂度空间复杂度代码实现四、堆排序时间复杂度空间复杂度代码实现五、冒泡...
    99+
    2024-04-02
  • C/C++语言八大排序算法之桶排序全过程示例详解
    基本思路是将所有数的个位十位百位一直到最大数的最高位一步步装桶,先个位装桶然后出桶,直到最高位入桶出桶完毕。 首先我们要求出一个数组的最大数然后求出他的最大位数  //...
    99+
    2024-04-02
软考高级职称资格查询
编程网,编程工程师的家园,是目前国内优秀的开源技术社区之一,形成了由开源软件库、代码分享、资讯、协作翻译、讨论区和博客等几大频道内容,为IT开发者提供了一个发现、使用、并交流开源技术的平台。
  • 官方手机版

  • 微信公众号

  • 商务合作