2.3 數組相關面試題
- 原地移除數組中所有的元素val，要求時間復雜度為O(N)，空間復雜度為O(1)。OJ鏈接
力扣OJ鏈接-移除元素 - 刪除排序數組中的重復項。力扣OJ鏈接-刪除有序數組中的重復項
- 合并兩個有序數組。力扣OJ鏈接-合并兩個有序數組
2.3.1 移除元素
1. 題目描述
力扣OJ鏈接-移除元素
原地移除數組中所有的元素val，要求時間復雜度為O(N)，空間復雜度為O(1)。
給你一個數組 nums 和一個值 val，你需要 原地 移除所有數值等于 val 的元素。元素的順序可能發生改變。然后返回 nums 中與 val 不同的元素的數量。
假設 nums 中不等于 val 的元素數量為 k，要通過此題，您需要執行以下操作：
- 更改 nums 數組，使 nums 的前 k 個元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
- 返回 k。
2. 分析
思路1：另外開辟一個數組，src從頭往后遍歷，遇到不是要刪除元素，就把該元素賦值給數組，直到遍歷完整個數組，在最后再把數組賦值到原數組。
思路2：不另外開辟數組就在原數組進行操作
src從前往后遍歷，遇到不等于val的數就賦值給dst
然后src++ ，dst++
src遇到val ,不進行賦值，直接src++，dst不變
直到src遍歷完整個數組
3. 思路2代碼實現
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++];}else{src++;}}return dst;
}
2.3.2 刪除重復元素
1. 題目描述
力扣OJ鏈接-刪除有序數組中的重復項
給你一個 非嚴格遞增排列 的數組 nums ，請你 原地 刪除重復出現的元素，使每個元素 只出現一次 ，返回刪除后數組的新長度。元素的 相對順序 應該保持 一致 。然后返回 nums 中唯一元素的個數。
考慮 nums 的唯一元素的數量為 k ，你需要做以下事情確保你的題解可以被通過：
- 更改數組 nums ，使 nums 的前 k 個元素包含唯一元素，并按照它們最初在 nums 中出現的順序排列。nums 的其余元素與nums 的大小不重要。
- 返回 k 。
2. 思路
這個和上一道題思路非常類似~重點是要分析，這個判斷相等如何設置。
3. 代碼實現
int removeDuplicates(int* nums, int numsSize) {int str = 1;int end = 0;while(str<numsSize){if(nums[str] != nums [end]){nums[++end] = nums[str++];//這里先++,如果后++，就會覆蓋原本的值}else{str++;} }return end+1;
}
進階寫法，雖然代碼量更短，但是代碼可讀性差~
int removeDuplicates(int* nums, int numsSize) {int str = 1;int end = 0;while(str<numsSize){if(nums[str] != nums [end])nums[++end] = nums[str++];//這里end必須先++,如果后++，就會覆蓋原本的值str++;} return end+1;
}
2.3.3 合并兩個有序數組
1.題目描述
力扣OJ鏈接-合并兩個有序數組
給你兩個按 非遞減順序 排列的整數數組 nums1 和 nums2，另有兩個整數 m 和 n ，分別表示 nums1 和 nums2 中的元素數目。
請你 合并 nums2 到 nums1 中，使合并后的數組同樣按 非遞減順序 排列。
注意：最終，合并后數組不應由函數返回，而是存儲在數組 nums1 中。為了應對這種情況，nums1 的初始長度為 m + n，其中前 m 個元素表示應合并的元素，后 n 個元素為 0 ，應忽略。nums2 的長度為 n 。
2. 思路
解題思路:
1. 從后往前遍歷數組，將nums1和nums2中的元素逐個比較
將較大的元素往nums1末尾進行搬移
2. 第一步結束后，nums2中可能會有數據沒有搬移完，將nums2中剩余的元素逐個搬移到nums1
時間復雜度：O(m+n)
空間復雜度: O(1)
兩種情況
情況1：
情況2
3. 代碼實現
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {// end1、end2：分別標記nums1 和 nums2最后一個有效元素位置// end標記nums1的末尾，因為nums1和nums2中的元素從后往前往nums1中存放// ，否則會存在數據覆蓋int end1 = m-1;int end2 = n-1;int dst = m+n-1;//合并后的數組長度是m + n，最后一個元素的位置就是 nums[m+n-1]// 從后往前遍歷，將num1或者nums2中較大的元素往num1中end位置搬移// 直到將num1或者num2中有效元素全部搬移完while(end1 >= 0 && end2 >= 0)//有一個小于1 就結束了，循環寫的是繼續，所以是&&{if(nums1[end1]>nums2[end2]){nums1[dst--] = nums1[end1--];}else{nums1[dst--]= nums2[end2--];}}// num2中的元素可能沒有搬移完，將剩余的元素繼續往nums1中搬移while(end2 >= 0){nums1[dst--] = nums2[end2--];}}
