題目描述
給定一個排序陣列，你需要在原地洗掉重復出現的元素，使得每個元素只出現一次，回傳移除后陣列的新長度，
不要使用額外的陣列空間，你必須在原地修改輸入陣列并在使用O（1）額外空間的條件下完成，
示例 1
給定陣列 nums = [1,1,2],
函式應該回傳新的長度 2, 并且原陣列 nums 的前兩個元素被修改為 1, 2，
你不需要考慮陣列中超出新長度后面的元素，
示例 2
給定 nums = [0,0,1,1,1,2,2,3,3,4],
函式應該回傳新的長度 5, 并且原陣列 nums 的前五個元素被修改為 0, 1, 2, 3, 4，
你不需要考慮陣列中超出新長度后面的元素，
說明:
為什么回傳數值是整數，但輸出的答案是陣列呢?
請注意，輸入陣列是以“ 參考 ”方式傳遞的，這意味著在函式里修改輸入陣列對于呼叫者是可見的，
你可以想象內部操作如下:
// nums 是以“參考”方式傳遞的，也就是說，不對實參做任何拷貝
int len = removeDuplicates(nums);
// 在函式里修改輸入陣列對于呼叫者是可見的，
// 根據你的函式回傳的長度, 它會列印出陣列中該長度范圍內的所有元素，
for (int i = 0; i < len; i++) {
print(nums[i]);
}
方法一：雙指標法
思路
陣列完成排序后，我們可以放置兩個指標 i 和 j ，其中 i 是慢指標，而 j 是快指標，只要nums[ i ] = nums[ j ] ，我們就增加 j 以跳過重復項，
當我們遇到nums[ j ] != num[ i ] 時，跳過重復項的運行已經結束，因此我們必須把它( nums[ j ] )的值復制到nums[ i + 1 ]，然后遞增 i，接著我們將再次重復相同的程序，直到 j 到達陣列的末尾為止，
題目要求兩件事：
- 統計陣列中不同數字數量 i ；
- 修改陣列前 i 個元素為這些不同數字，
演算法流程：
- 第一個指標 i ： 每遇到新的不同數字時，執行 i ++，i 指標有兩個作用：
1. 記錄陣列中不同數字的數量；
2. 作為修改陣列元素的索引，
- 第二個指標 i： 由于陣列已經完成排序，因此遍歷陣列，每遇到 nums[ j ] != num[ i ] ，就說明遇到了新的不同數字，記錄之；
- 最終，回傳 i + 1 即可，
代碼實作
class Solution {
public int removeDuplicates(int[] nums) {
if (nums.length == 0) {
return 0;
}
int i = 0;//定義一個指標變數
//遍歷陣列
for (int j = 1; j < nums.length; j++) {
//如果指標指向的元素不等于當前遍歷的元素
if (nums[i]!=nums[j] ){
//指標后移一位
i++;
//修改陣列，
nums[i] = nums[j];
}
}
//i初始值為0，由于要求陣列長度，故需要加1
return i + 1;
}
}
演算法圖解
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/114597.html
標籤：其他