雙指針

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

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

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

對撞指針

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

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

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

快慢指針

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

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

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

真題實戰(zhàn)

1.調整數(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;
}

這道題就是典型的對撞指針，我們遍歷完整個數(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;
}  

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

今天就到這里了，摸了家人們，情人節(jié)快樂！更多關于C語言雙指針算法的資料請關注腳本之家其它相關文章！

最新評論