目錄

一、刪除有序數(shù)組中的重復(fù)項(xiàng)，返回出現(xiàn)一次元素的個(gè)數(shù)。

二、原地移除數(shù)組中所有數(shù)值等于val的元素

三、合并兩個(gè)有序數(shù)組

四、旋轉(zhuǎn)數(shù)組

五、數(shù)組形式的整數(shù)加法

---

一、刪除有序數(shù)組中的重復(fù)項(xiàng)，返回出現(xiàn)一次元素的個(gè)數(shù)。

26. 刪除有序數(shù)組中的重復(fù)項(xiàng) - 力扣（LeetCode）

給你一個(gè)?非嚴(yán)格遞增排列?的數(shù)組?nums?，請(qǐng)你?原地?刪除重復(fù)出現(xiàn)的元素，使每個(gè)元素?只出現(xiàn)一次?，返回刪除后數(shù)組的新長(zhǎng)度。元素的?相對(duì)順序?應(yīng)該保持?一致?。然后返回?nums?中唯一元素的個(gè)數(shù)。數(shù)組大小numsSize已給出。

考慮?nums?的唯一元素的數(shù)量為?k?，你需要做以下事情確保你的題解可以被通過：

• 更改數(shù)組?nums?，使?nums?的前?k?個(gè)元素包含唯一元素，并按照它們最初在?nums?中出現(xiàn)的順序排列。nums?的其余元素與?nums?的大小不重要。
• 返回?k?。

int removeDuplicates(int* nums, int numsSize) {int src = 1;int dst = 0;while (src < numsSize) {if (nums[src] == nums[dst])src++;elsenums[++dst] = nums[src++];}return dst + 1;
}

思路：采用雙指針一前一后

1、src負(fù)責(zé)尋找與當(dāng)前dst相等的值，dst負(fù)責(zé)修改數(shù)組。

2、如果src等于dst，則src向后移動(dòng)一位，向后尋找不相同的值

3、如果src不等于dst，則dst向后移動(dòng)一位，將src的值賦值給dst，src向后移動(dòng)一位繼續(xù)循環(huán)比較后項(xiàng)元素。

4、src指向數(shù)組最后一個(gè)元素時(shí)，比較后src大于數(shù)組大小numsSize時(shí)停止循環(huán)。

5、返回值為新數(shù)組的大小dst+1。

二、原地移除數(shù)組中所有數(shù)值等于val的元素

27. 移除元素 - 力扣（LeetCode）

給你一個(gè)數(shù)組?nums?和一個(gè)值?val，你需要?原地?移除所有數(shù)值等于?val?的元素，并返回移后數(shù)組的新長(zhǎng)度。

不要使用額外的數(shù)組空間，你必須僅使用?O(1)?額外空間并?原地?修改輸入數(shù)組。

元素的順序可以改變。你不需要考慮數(shù)組中超出新長(zhǎng)度后面的元素。

int removeElement(int* nums, int numsSize, int val) {int src = 0;int dst = 0;while (src < numsSize) {if (nums[src] != val)nums[dst++] = nums[src++];elsesrc++;}return dst;
}

思路：采用雙指針

src負(fù)責(zé)尋找值為val的位置，dst負(fù)責(zé)修改數(shù)組。假設(shè)當(dāng)前val等于7。

1、如果src不等于val，則dst賦值為src，然后整體向后移動(dòng)。

2、如果src等于val（dst也等于val），src向后移動(dòng)一位。

3、再次判斷時(shí)src不等于val，dst(當(dāng)前為val)被賦值為src(val后一項(xiàng))。成功刪除數(shù)組元素val。

4、刪除后dst和src均向后移動(dòng)一位 。

5、之后在數(shù)組中依次查找，沒有等于val的元素則將src賦值給dst（后項(xiàng)值一次賦值給前項(xiàng)），賦值后二者向后移動(dòng)一位。

結(jié)果如下：

6、最終返回?cái)?shù)組長(zhǎng)度dst。

三、合并兩個(gè)有序數(shù)組

88.?合并兩個(gè)有序數(shù)組

給你兩個(gè)按?非遞減順序?排列的整數(shù)數(shù)組?nums1?和?nums2，另有兩個(gè)整數(shù)?m?和?n?，分別表示?nums1?和?nums2?中的元素?cái)?shù)目。

請(qǐng)你?合并?nums2?到?nums1?中，使合并后的數(shù)組同樣按?非遞減順序?排列。

注意：最終，合并后數(shù)組不應(yīng)由函數(shù)返回，而是存儲(chǔ)在數(shù)組?nums1?中。為了應(yīng)對(duì)這種情況，nums1?的初始長(zhǎng)度為?m + n，其中前?m?個(gè)元素表示應(yīng)合并的元素，后?n?個(gè)元素為?0?，應(yīng)忽略。nums2?的長(zhǎng)度為?n?。

示例 1：

輸入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
輸出：[1,2,2,3,5,6]

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {int end1 = m - 1;int end2 = n - 1;int i = m + n - 1;while (end1 >= 0 && end2 >= 0) {if (nums2[end2] > nums1[end1])nums1[i--] = nums2[end2--];else {nums1[i--] = nums1[end1--];}}while (end2 >= 0)nums1[i--] = nums2[end2--];
}

思路：三指針法

假設(shè)合并這兩個(gè)數(shù)組：

1、定義 end1 和 end2 分別為數(shù)組 num1 和 num2 的最后一個(gè)元素下標(biāo)，定義 i 為合并后num1新的最后一個(gè)元素下標(biāo).

2、因?yàn)槭沁f增數(shù)列，所以我們從后向前先比較兩個(gè)數(shù)組最后一個(gè)元素 (最大元素) 的大小。

大的元素賦值給數(shù)組num1尾節(jié)點(diǎn)，然后將 i、end1和end2向前移動(dòng)一位繼續(xù)比較。

3、如果end2位置元素不大于end1位置元素，則將end1位置元素賦值給 i 位置，end1和 i 向前移動(dòng)一位。

4、最后end1已將小于零時(shí)，end2還等于0，證明數(shù)組num2中還有未合并的元素且該元素小于num1中最小元素（首元素）。

?

5、我們通過第二個(gè)循環(huán)將數(shù)組num2中小于num1最小元素的元素賦值到num1剩余位置，end2小于零時(shí)賦值結(jié)束。

?當(dāng)然也可以使用qsot排序做這道題，但時(shí)間復(fù)雜度為O(nlogn)大于上述解法的O(m+n)。

?所以綜合考慮推薦三指針法！！！

?四、旋轉(zhuǎn)數(shù)組

189. 輪轉(zhuǎn)數(shù)組 - 力扣（LeetCode）

給定一個(gè)整數(shù)數(shù)組?nums，將數(shù)組中的元素向右輪轉(zhuǎn)?k?個(gè)位置，其中?k?是非負(fù)數(shù)。

示例 1:

輸入: nums = [1,2,3,4,5,6,7], k = 3
輸出: [5,6,7,1,2,3,4]
解釋:
向右輪轉(zhuǎn) 1 步: [7,1,2,3,4,5,6]
向右輪轉(zhuǎn) 2 步: [6,7,1,2,3,4,5]
向右輪轉(zhuǎn) 3 步: [5,6,7,1,2,3,4]

void reserve(int* a, int left, int right)
{while (left < right) {int tmp = a[left];a[left] = a[right];a[right] = tmp;left++;right--;}
}
void rotate(int* nums, int numsSize, int k) {if (k > numsSize)k %= numsSize;reserve(nums, numsSize - k, numsSize - 1);reserve(nums, 0, numsSize - k - 1);reserve(nums, 0, numsSize - 1);
}

思路：使用三次逆轉(zhuǎn)法，讓數(shù)組旋轉(zhuǎn)k次

• 逆轉(zhuǎn)子數(shù)組[numsSize - k, numsSize - 1]
• 逆轉(zhuǎn)子數(shù)組[0, numsSize - k - 1]
• 整體逆轉(zhuǎn)[0,numsSize -?1]

假設(shè)輪轉(zhuǎn)次數(shù)k為3?

1、首先寫出逆轉(zhuǎn)數(shù)組的函數(shù)reserve，逆置的原理就是依次交換首尾元素。

?2、然后找到要逆轉(zhuǎn)的數(shù)組對(duì)應(yīng)部分進(jìn)行逆轉(zhuǎn)。

3、 逆轉(zhuǎn)過程如下：

五、數(shù)組形式的整數(shù)加法

?989. 數(shù)組形式的整數(shù)加法 - 力扣（LeetCode）

整數(shù)的?數(shù)組形式??num?是按照從左到右的順序表示其數(shù)字的數(shù)組。

• 例如，對(duì)于?num = 1321?，數(shù)組形式是?[1,3,2,1]?。

給定?num?，整數(shù)的?數(shù)組形式?，和整數(shù)?k?，返回?整數(shù)?num + k?的?數(shù)組形式?。

示例 1：

輸入：num = [1,2,0,0], k = 34
輸出：[1,2,3,4]
解釋：1200 + 34 = 1234

int* addToArrayForm(int* A, int ASize, int K, int* returnSize) {int* addRet = (int*)malloc(10001 * sizeof(int));//reti: 第i位的結(jié)果int reti = 0;//從低位開始相加int ai = ASize - 1;int next = 0; // 進(jìn)位值while (ai >= 0 || K > 0){int x1 = 0;//如果ai沒有越界，還有未相加的位，取出一位存入x1if (ai >= 0){x1 = A[ai];--ai;}int x2 = 0;//如果k大于0，獲取k的第i位if (K > 0){x2 = K % 10;K /= 10;}//第i位的結(jié)果：每一位的值 + 進(jìn)位int ret = x1 + x2 + next;//如果結(jié)果大于9，需要進(jìn)位if (ret > 9){ret %= 10;next = 1;}else{next = 0;}//存入第i位的結(jié)果到數(shù)組中addRet[reti++] = ret;}//如果最高位有進(jìn)位，需要在存入1if (next == 1){addRet[reti++] = 1;}//逆置結(jié)果reverse(addRet, 0, reti - 1);*returnSize = reti;return addRet;
}

?思路：模擬加法進(jìn)行逐位相加， 從低位向高位相加，最后整體逆置，得到最終結(jié)果

1、定義一個(gè)整數(shù)數(shù)組?addRet?用于存儲(chǔ)相加的結(jié)果。數(shù)組的大小設(shè)為10001，足夠容納可能的最大結(jié)果。

定義變量?reti，表示結(jié)果數(shù)組的當(dāng)前索引，初始化為0。

定義變量?ai，表示數(shù)組?A?的當(dāng)前索引，初始化為?ASize - 1，即數(shù)組?A?的最高索引。

定義變量?next，表示進(jìn)位值，初始化為0。

int* addRet = (int*)malloc(10001 * sizeof(int));
int reti = 0;
int ai = ASize - 1;
int next = 0; 

2、使用循環(huán)處理每一位的相加，循環(huán)條件是?ai >= 0?或?K > 0，即數(shù)組?A?還有位數(shù)未相加，或者?K?還有位數(shù)未相加。

while (ai >= 0 || K > 0)

3、在循環(huán)內(nèi)部，首先獲取?A?數(shù)組當(dāng)前位的值?x1，如果?ai?沒有越界，就取出對(duì)應(yīng)位置的值，并將?ai?減1。

int x1 = 0;
if (ai >= 0)
{x1 = A[ai];--ai;
}

4、獲取整數(shù)?K?的當(dāng)前位值?x2，如果?K?大于0，就取出?K?的最低位，同時(shí)將?K?除以10，以準(zhǔn)備處理下一位。

 int x2 = 0;if (K > 0){x2 = K % 10;K /= 10;}

5、計(jì)算當(dāng)前位的結(jié)果?ret，是?x1、x2?和之前的進(jìn)位?next?三者之和。如果結(jié)果大于9，表示需要進(jìn)位，就對(duì)結(jié)果取模10，然后將?next?設(shè)置為1；否則，next?設(shè)置為0。

int ret = x1 + x2 + next;
if (ret > 9)
{ret %= 10;next = 1;
}
else
{next = 0;
}

7、將計(jì)算得到的?ret?存入結(jié)果數(shù)組?addRet?的當(dāng)前位置?reti，遞增?reti，以準(zhǔn)備處理下一位。

addRet[reti++] = ret;

8、循環(huán)結(jié)束后，檢查最高位是否有進(jìn)位。如果?next?為1，表示有進(jìn)位，因此將1存入結(jié)果數(shù)組的當(dāng)前位置?reti。

 if (next == 1){addRet[reti++] = 1;}

9、調(diào)用?reverse?函數(shù)來逆置結(jié)果數(shù)組?addRet，以得到正確的結(jié)果順序。

reverse(addRet, 0, reti - 1);

最后，將結(jié)果數(shù)組的大小?reti?賦值給?returnSize?指向的變量，以告知結(jié)果數(shù)組的大小。

返回結(jié)果數(shù)組?addRet，它包含了相加的結(jié)果。

*returnSize = reti;
return addRet;