本章我們介紹的兩類練習題主要是關于C語言實作資料結構的複雜度和順序表類問題。
1、異或的巧妙應用
我們刷題時候經常會遇到去重類的問題，更讓人頭疼的是有空間複雜度的限制，這就意味着我們不能重新建立一個數組用條件語句存放，是以這裡我們巧妙地借用異或語句來實作。
在做題之前我們先來看一下異或的一些特點：
1、0和任何數異或還是那個數本身。
我們用5舉例：
2、異或具有交換律。
比如1^2^3=1^3^2.
3、兩個相同的數異或結果為0。
因為異或的定義是相同為0，相異為1，兩個相同的數每個比特位上的值肯定一樣，是以為0.
ok，有了上面的幾個特點，我們來來一下下面的題目：
找單身狗：
一個數組中隻有兩個數字是出現一次，其他所有數字都出現了兩次。
編寫一個函數找出這兩個隻出現一次的數字。空間複雜度為O(1)。
對于這道題，如果隻有一個數字隻出現一次，我們可以把所有數字和0異或，出現兩次的數字就會被異或成0，然後我們最後得到的數字就是隻出現一次的數字（典型單身狗問題）。
但是這題要求找出兩個隻出現一次的數字，我們怎麼辦呢？
比如對于這樣一組數字，我們把所有異或在一起，好像得到的數字也無法解讀處5和6，那麼我們思考可不可以分組呢？
我們分成這樣的兩組，然後每一組中在内部異或，第一組就可以找出5，第二組就可以找出6，那麼如何實作這樣的分組異或呢？
這裡的分組不一定要這樣分，其實隻需要把5和6分為兩組即可。這裡我們想到，把所有數異或和0後得到的數就是5和6異或後的數字，我們從比特位的角度來看，每次右移一次然後和1進行&運算，隻要結果為1，那麼就是5和6這位比特位上數字不一樣，我們就可以通過這一特點分組。
然後我們利用循環曆遍每一個數，對于每一個數利用位移操作符右移上面記錄的pos個位置，然後和1&運算，隻要為1就一起異或，為0在另一組異或，兩組異或出的答案就是兩個尋找的數。
請看代碼：
#include<stdio.h>
int main()
{
int arr[] = { 1,2,3,4,5,1,2,3,4,7 };
int sz = sizeof(arr) / sizeof(arr[0]);
int i = 0;
int ret = 0;
for(i=0;i<sz;i++)
{
ret ^= arr[i];
}
int pos = 0;
for (i = 0; i < 32; i++)
{
if (((ret >>i) & 1) == 1)
{
pos = i;
break;
}
}
int num1 = 0;
int num2 = 0;
for (i = 0; i < sz; i++)
{
if (((arr[i] >> pos) & 1) == 1)
num1 ^= arr[i];
else
num2 ^= arr[i];
}
printf("%d %d",num1,num2);
return 0;
}
2、順序表相關OJ練習題（雙指針問題）
1、力扣
https://leetcode.cn/problems/remove-element/
給你一個數組 nums 和一個值 val，你需要 原地 移除所有數值等于 val 的元素，并傳回移除後數組的新長度。
不要使用額外的數組空間，你必須僅使用 O(1) 額外空間并 原地 修改輸入數組。
元素的順序可以改變。你不需要考慮數組中超出新長度後面的元素。
這道題大家初始都會想再建立一個數組 ，但是空間複雜度的限制否決了我們這一想法。
是以我們怎麼能在目前數組上進行改動呢？這裡我們可以利用雙指針了：
p1和p2都先指向第一個元素，然後p1往前走，在看第二個位置和p2一不一樣，如果不一樣，p2也往前走：
然後p1再走，不一樣，p2再走：
下一步我們發現，p1走後和p2比較，相等，那p2就不動，直到p1走到3後和p2不一樣，然後p2再走，然後把3指派給p2所在位置：
下面以此類推，這就是典型的快慢指針問題。
下面我們給出解答：
int removeElement(int* nums, int numsSize, int val){
int p1=0;
int p2=0;
while(p1<numsSize)
{
if(nums[p1]!=val)
{
nums[p2]=nums[p1];
p1++;
p2++;
}
else if(nums[p1]==val)
{
p1++;
}
}
return p2;
}
2、
力扣
https://leetcode.cn/problems/remove-duplicates-from-sorted-array/
給你一個 升序排列 的數組 nums ，請你 原地 删除重複出現的元素，使每個元素 隻出現一次 ，傳回删除後數組的新長度。元素的 相對順序 應該保持 一緻 。
由于在某些語言中不能改變數組的長度，是以必須将結果放在數組nums的第一部分。更規範地說，如果在删除重複項之後有 k 個元素，那麼 nums 的前 k 個元素應該儲存最終結果。
将最終結果插入 nums 的前 k 個位置後傳回 k 。
不要使用額外的空間，你必須在 原地 修改輸入數組 并在使用 O(1) 額外空間的條件下完成。
這道題也是去重類的問題，但是并不能用上面的異或來考慮的了，因為要保留重複的數字。我們延續雙指針的想法，p1和p2同時指向第一個元素，p1++，和p2比較，一樣的話p2就不動，不一樣p2++并把p1指向的元素值指派給p2指向的元素值。這樣就可完成了。
最後傳回的是長度，也就是p2+1。
請看代碼：
int removeDuplicates(int* nums, int numsSize){
int p1=0;
int p2=0;
while(p1<numsSize)
{if(nums[p1]==nums[p2])
{
++p1;
}
else if(nums[p1]!=nums[p2])
{
++p2;
nums[p2]=nums[p1];
++p1;
}
}
return p2+1;
}
3、力扣
https://leetcode.cn/problems/merge-sorted-array/
給你兩個按 非遞減順序 排列的整數數組 nums1 和 nums2，另有兩個整數 m 和 n ，分别表示 nums1 和 nums2 中的元素數目。
請你 合并 nums2 到 nums1 中，使合并後的數組同樣按 非遞減順序 排列。
注意：最終，合并後數組不應由函數傳回，而是存儲在數組 nums1 中。為了應對這種情況，nums1 的初始長度為 m + n，其中前 m 個元素表示應合并的元素，後 n 個元素為 0 ，應忽略。nums2 的長度為 n 。
這道題我們延續上面的思路的話可能導緻一些資料的覆寫，是以我們再另尋他法。
我們發現例題中nums1後面是0，我們思考可不可以從後往前曆遍呢？
比上面多一個指針，三指針解決這道題。
end1和end2比較大的就放在end處
然後end--，放完元素的指針也向前找。
考慮特殊情況，如果nums1元素都找完了，end1指向0位置，而end2還沒有指向0位置，那麼就把nums2剩餘的元素拷貝到nums1中就ok了。
請看代碼：
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
int end=m+n-1;
int end1=m-1;
int end2=n-1;
while(end1>=0&&end2>=0)
{
if(nums1[end1]<=nums2[end2])
{
nums1[end--]=nums2[end2--];
}
else if(nums1[end1]>nums2[end2])
{
nums1[end--]=nums1[end1--];
}
}
while(end2>=0)
{
nums1[end--]=nums2[end2--];
}
}