日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

C語言雙指針算法朋友過情人節我過算法_C 語言

作者：喬喬家的龍龍 ? 更新時間： 2022-04-19 編程語言

雙指針

首先咱得知道何為雙指針，聽起來很上流，其實有手就行。

雙指針，指的是在遍歷對象的過程中，不是普通的使用單個指針進行訪問，而是使用兩個相同方向（快慢指針）或者相反方向（對撞指針）的指針進行掃描，從而達到相應的目的。

換言之，雙指針法充分使用了數組有序這一特征，當遇到有序數組時，應該優先想到雙指針來解決問題，因兩個指針的同時遍歷會減少空間復雜度和時間復雜度從而在某些情況下能夠簡化運算

在這里插入圖片描述

對撞指針

類似于相遇問題，對撞指針是指在有序數組中，將指向最左側的索引定義為左指針，最右側的定義為右指針，然后分別從兩側出發，相向遍歷鏈表，這個過程就形象化為對撞，習慣上就將左右指針定義為 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)。

原文鏈接：https://blog.csdn.net/qq_61500888/article/details/122258697?spm=1001.2014.3001.5502

欄目分類
最近更新