C語言雙指標演演算法朋友過情人節我過演演算法

2022-02-14 16:00:17

雙指標

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

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

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

對撞指標

類似於相遇問題，對撞指標是指在有序陣列中，將指向最左側的索引定義為左指標，最右側的定義為右指標，然後分別從兩側出發，相向遍歷連結串列，這個過程就形象化為對撞，習慣上就將左右指標定義為 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語言雙指標演演算法的資料請關注it145.com其它相關文章！

C語言雙指標演演算法朋友過情人節我過演演算法

目錄

雙指標

對撞指標

快慢指標

真題實戰

熱門文章