Q26RemoveDuplicatesFromSortedArray
題目描述
給你一個升序排列的陣列 nums ，請你原地洗掉重復出現的元素，使每個元素 只出現一次 ，回傳洗掉后陣列的新長度，元素的相對順序應該保持 一致 ，
由于在某些語言中不能改變陣列的長度，所以必須將結果放在陣列nums的第一部分，更規范地說，如果在洗掉重復項之后有k個元素，那么 nums 的前k個元素應該保存最終結果，
將最終結果插入nums的前k個位置后回傳k，
不要使用額外的空間，你必須在原地修改輸入陣列,并在使用O(1)額外空間的條件下完成，
判題標準:
系統會用下面的代碼來測驗你的題解:
int[] nums = [...]; // 輸入陣列
int[] expectedNums = [...]; // 長度正確的期望答案
int k = removeDuplicates(nums); // 呼叫
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,_]
解釋：函式應該回傳新的長度 2 ，并且原陣列 nums 的前兩個元素被修改為 1, 2 ，不需要考慮陣列中超出新長度后面的元素，
示例 2：
輸入：nums = [0,0,1,1,1,2,2,3,3,4]
輸出：5, nums = [0,1,2,3,4]
解釋：函式應該回傳新的長度 5 ， 并且原陣列 nums 的前五個元素被修改為 0, 1, 2, 3, 4 ，不需要考慮陣列中超出新長度后面的元素，
https://leetcode.cn/problems/remove-duplicates-from-sorted-array
解題思路
題目要求是原地修改陣列，即不能構造新陣列，且時間為O(1)
考慮到陣列是有序的，即相等元素的下標一定是連續的，可以考慮使用雙指標來解題，
定義fast和slow兩個指標，fast指向當前遍歷到的元素，slow指標指向構造好的陣列的最后一個位置，兩個指標從0開始，fast指標從0遍歷到len-1，對于遍歷到的每個元素，判斷nums[fast] 與 nums[slow] 是否一致，如果不一致則表明當前元素為新的不同元素，將其放入 nums[++slow] 中，slow仍指向構造好的陣列最后一個位置，最后將slow加一為陣列長度回傳，
代碼
public class Q26RemoveDuplicatesFromSortedArray {
public int removeDuplicates(int[] nums) {
if(nums==null || nums.length==0){
return 0;
}
int len = nums.length;
int fast = 0;
int low = 0;
while(fast < len){
if(nums[fast] != nums[low]){
nums[++low] = nums[fast];
}
fast++;
}
return ++low;
}
}
本地測驗
public class Q26RemoveDuplicatesFromSortedArrayTest {
private Q26RemoveDuplicatesFromSortedArray q = new Q26RemoveDuplicatesFromSortedArray();
@Test
public void test1() {
int[] test = new int[]{1,1,2};
assertEquals(2, q.removeDuplicates(test));
assertArrayEquals(new int[]{1,2,2}, test);
}
@Test
public void test2() {
int[] test = new int[]{0,0,1,1,1,2,2,3,3,4};
assertEquals(5, q.removeDuplicates(test));
assertArrayEquals(new int[]{0,1,2,3,4,2,2,3,3,4}, test);
}
}
提交
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/501352.html
標籤：其他
上一篇：線段樹學習筆記（原洛谷文章）