每日一道 LeetCode (8)：刪除排序數(shù)組中的重復(fù)項和移除元素
?每天 3 分鐘，走上算法的逆襲之路。
?
前文合集
代碼倉庫
GitHub：https://github.com/meteor1993/LeetCode
Gitee：https://gitee.com/inwsy/LeetCode
引言
今天破例兩道題，原因是我做完第一道題感覺有點簡單，順手看了下后面的那道題，發(fā)現(xiàn)這兩道題的思路是一致的，就合在一起了。
題目：刪除排序數(shù)組中的重復(fù)項
題目來源：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/
給定一個排序數(shù)組，你需要在 原地 刪除重復(fù)出現(xiàn)的元素，使得每個元素只出現(xiàn)一次，返回移除后數(shù)組的新長度。
不要使用額外的數(shù)組空間，你必須在 原地 修改輸入數(shù)組 并在使用 O(1) 額外空間的條件下完成。
示例 1:
給定數(shù)組 nums = [1,1,2],
函數(shù)應(yīng)該返回新的長度 2, 并且原數(shù)組 nums 的前兩個元素被修改為 1, 2。
你不需要考慮數(shù)組中超出新長度后面的元素。
示例2：
給定 nums = [0,0,1,1,1,2,2,3,3,4],
函數(shù)應(yīng)該返回新的長度 5, 并且原數(shù)組 nums 的前五個元素被修改為 0, 1, 2, 3, 4。
你不需要考慮數(shù)組中超出新長度后面的元素。
解題：刪除排序數(shù)組中的重復(fù)項
這道題是少有的簡單題，我的這個簡單題是經(jīng)過思考，很輕易的就能想出解決方案。
這道題的難點其實只有一個 「不要使用額外的數(shù)組空間，必須修改原數(shù)組的條件下完成。」 。
如果沒有這個限制條件，我覺得每一位剛接觸編程的同學(xué)都能完成這個任務(wù)。
先說說沒有限制條件的做法，直接新開一個數(shù)組，然后循環(huán)給定的數(shù)組 nums ，遇到符合條件的直接塞到新數(shù)組里面。
但是如果限制了空間使用，只能在原數(shù)組上做操作，這個就稍微有點困難了。
不過還好的是，示例里面只要求我們原數(shù)組的前 n 個元素正確就好了，后面的元素?zé)o需考慮。
給定的數(shù)組本身是有序的，那么如果數(shù)組長度只有 0 或者是 1 的時候，我們的程序是不需要做操作的，直接返回就好了，這樣，第一個極限值判斷條件就出來了。
接下來就是我們?nèi)绾卧谝粋€數(shù)組中進(jìn)行操作，將重復(fù)的值去掉了。
因為我們的目標(biāo)是獲取一個沒有重復(fù)元素的數(shù)組，所以事情就很簡單了，定義兩個指針：j ?和 i ，我們循環(huán)數(shù)組，開始移動 i ，只要發(fā)現(xiàn) j ?和 i 指向的元素不相同，就把 i 賦值給 j ，然后 ++j 后繼續(xù)循環(huán)，直到循環(huán)結(jié)束。
簡單畫個圖解釋下：
這幅圖先不解釋，直接上代碼：
public int removeDuplicates(int[] nums) {
if (nums.length < 2) return nums.length;
int j = 0;
for (int i = 1; i < nums.length; i++) {
if (nums[j] != nums[i]) {
nums[++j] = nums[i];
}
}
return ++j;
}
上面圖沒理解的對著這段代碼看，注意我里面的賦值操作，當(dāng)發(fā)現(xiàn) i 和 j 不一樣以后，我把 i 的值賦值給了 ++j ，意思就是 j 的下一位。
好了，這個題沒有其他滑頭了結(jié)束了。
題目：移除元素
題目來源：https://leetcode-cn.com/problems/remove-element/
給你一個數(shù)組 nums 和一個值 val，你需要 原地 移除所有數(shù)值等于 val 的元素，并返回移除后數(shù)組的新長度。
不要使用額外的數(shù)組空間，你必須僅使用 O(1) 額外空間并 原地 修改輸入數(shù)組。
元素的順序可以改變。你不需要考慮數(shù)組中超出新長度后面的元素。
示例 1:
給定 nums = [3,2,2,3], val = 3,
函數(shù)應(yīng)該返回新的長度 2, 并且 nums 中的前兩個元素均為 2。
你不需要考慮數(shù)組中超出新長度后面的元素。
示例 2:
給定 nums = [0,1,2,2,3,0,4,2], val = 2,
函數(shù)應(yīng)該返回新的長度 5, 并且 nums 中的前五個元素為 0, 1, 3, 0, 4。
注意這五個元素可為任意順序。
你不需要考慮數(shù)組中超出新長度后面的元素。
解題：移除元素
這道題的限制和前面一道題完全一樣，都是不允許開新的數(shù)組，要在原數(shù)組解決。
解題思路也和前面的一道題非常非常像，像到我都不好意思說這是兩道題。
這道題的目標(biāo)是找到所有的目標(biāo)值，然后 「移除」 出去，實際上是把這個值扔到后面去，我們只需要保證前面的值正確就行。
思路和上面完全一致，同樣是開兩個指針 j 和 i ，然后開始循環(huán)數(shù)組，當(dāng)遇到和目標(biāo)值不一樣的，我們把這個值放到 j 的位置，并且讓 j 向后移動一位，直至循環(huán)結(jié)束。
上代碼輔助理解：
public int removeElement(int[] nums, int val) {
int j = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != val) {
nums[j] = nums[i];
j++;
}
}
return j;
}
這兩道題題我就不多做解釋了，如果實在搞不懂的， debug 一下上面的代碼，保證你分分鐘理解清楚。
