算法之刪除有序數(shù)組中的重復(fù)項
題目:
給你一個 升序排列 的數(shù)組 nums ,請你 原地 刪除重復(fù)出現(xiàn)的元素,使每個元素 只出現(xiàn)一次 ,返回刪除后數(shù)組的新長度。元素的 相對順序 應(yīng)該保持 一致 。
由于在某些語言中不能改變數(shù)組的長度,所以必須將結(jié)果放在數(shù)組nums的第一部分。更規(guī)范地說,如果在刪除重復(fù)項之后有 k 個元素,那么 nums 的前 k 個元素應(yīng)該保存最終結(jié)果。
將最終結(jié)果插入 nums 的前 k 個位置后返回 k 。
不要使用額外的空間,你必須在 原地 修改輸入數(shù)組 并在使用 O(1) 額外空間的條件下完成。
判題標準:
系統(tǒng)會用下面的代碼來測試你的題解:
int[] nums = [...]; // 輸入數(shù)組
int[] expectedNums = [...]; // 長度正確的期望答案
int k = removeDuplicates(nums); // 調(diào)用
assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
? ? assert nums[i] == expectedNums[i];
}
如果所有斷言都通過,那么您的題解將被 通過。
示例 1:
輸入:nums = [1,1,2]
輸出:2, nums = [1,2,_]
解釋:函數(shù)應(yīng)該返回新的長度 2 ,并且原數(shù)組 nums 的前兩個元素被修改為 1, 2 。不需要考慮數(shù)組中超出新長度后面的元素。
示例 2:
輸入:nums = [0,0,1,1,1,2,2,3,3,4]
輸出:5, nums = [0,1,2,3,4]
解釋:函數(shù)應(yīng)該返回新的長度 5 , 并且原數(shù)組 nums 的前五個元素被修改為 0, 1, 2, 3, 4 。不需要考慮數(shù)組中超出新長度后面的元素。
提示:
1 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按 升序 排列
我的答案:
我的解析:
使用雙索引,j指向等待被賦值的下標,i遍歷數(shù)組,尋找允許留下的值放到j(luò)處。最終的j就是答案本身,代表j左邊有多少個數(shù)。