雙指針

首先咱得知道何為雙指針，聽(tīng)起來(lái)很上流，其實(shí)有手就行。

雙指針，指的是在遍歷對(duì)象的過(guò)程中，不是普通的使用單個(gè)指針進(jìn)行訪問(wèn)，而是使用兩個(gè)相同方向（快慢指針）或者相反方向（對(duì)撞指針）的指針進(jìn)行掃描，從而達(dá)到相應(yīng)的目的。

換言之，雙指針?lè)ǔ浞质褂昧藬?shù)組有序這一特征，當(dāng)遇到有序數(shù)組時(shí)，應(yīng)該優(yōu)先想到雙指針來(lái)解決問(wèn)題，因兩個(gè)指針的同時(shí)遍歷會(huì)減少空間復(fù)雜度和時(shí)間復(fù)雜度從而在某些情況下能夠簡(jiǎn)化運(yùn)算

對(duì)撞指針

類似于相遇問(wèn)題，對(duì)撞指針是指在有序數(shù)組中，將指向最左側(cè)的索引定義為左指針，最右側(cè)的定義為右指針，然后分別從兩側(cè)出發(fā)，相向遍歷鏈表，這個(gè)過(guò)程就形象化為對(duì)撞，習(xí)慣上就將左右指針定義為 left 和 right，我們給出一個(gè)大致代碼邏輯：

void hit(int *arr,int arrsize)
{
int* left = arr;
int* right = arr + arrsize -1;
while(left<=right)
{
條件語(yǔ)句;
left++;
條件語(yǔ)句;
right--;
}
}

對(duì)撞指針適用于二分查找，鏈表對(duì)象求和等，也就是說(shuō)當(dāng)你遇到題目給定有序數(shù)組時(shí)，應(yīng)該第一時(shí)間想到的思路就是使用對(duì)撞指針。

快慢指針

類似于龜兔賽跑，快慢指針是兩個(gè)鏈表上的指針從同一節(jié)點(diǎn)出發(fā)，其中一個(gè)指針前進(jìn)速度比另一個(gè)快，兩個(gè)指針以不同的策略移動(dòng)，直到兩個(gè)指針的值達(dá)成某個(gè)條件為止，如圖（ppt繪圖+手殘勿噴）：

我們同樣將左右指針定義為 slow，fast，要實(shí)現(xiàn)其中一個(gè)指針比另一個(gè)快，我們無(wú)可厚非就兩種方法：

1.同時(shí)起步，fast 比 slow 多走n步；

2.fast 先走，slow后走；

那我們給出他的邏輯代碼：
同時(shí)走：

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++;
}
}

真題實(shí)戰(zhàn)

1.調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面

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;
}

這道題就是典型的對(duì)撞指針，我們遍歷完整個(gè)數(shù)組時(shí)，左右指針路程各自一半，只需要 left 尋找奇數(shù)，right 尋找偶數(shù)做交換即可。

==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;
}  

這是典型的快慢指針，第一個(gè)指針用來(lái)遍歷數(shù)組元素，判斷是不是要?jiǎng)h除的數(shù)，第二個(gè)指針用來(lái)存放數(shù)字。如果第一個(gè)指針指向的是要?jiǎng)h除的元素，那么輸出用來(lái)存放輸出數(shù)組元素個(gè)數(shù)的整形變量sz就自減 1，然后第一個(gè)指針向后移動(dòng)一位，第二個(gè)指針不動(dòng)；如果第一個(gè)指針指向的不是要?jiǎng)h除的數(shù)，那么就把這個(gè)數(shù)放到第二個(gè)指針指向的位置，然后第一個(gè)指針和第二個(gè)指針都向后移動(dòng)一位。重復(fù)操作直到第一個(gè)指針遍歷整個(gè)數(shù)組，此方法的時(shí)間復(fù)雜度是O(n)。

今天就到這里了，摸了家人們，情人節(jié)快樂(lè)！更多關(guān)于C語(yǔ)言雙指針?biāo)惴ǖ馁Y料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論