Categories
All 算法

做題筆記:Remove Duplicates from Sorted Array (Java)

今後 Easy 題若沒碰到非常精彩的就不每題都更了。

題目描述:

給定一個按非遞減順序排序的整數數組 nums,就地刪除重複項,使每個單獨的元素只出現一次。元素的相對順序應保持不變。

由於在某些語言中無法更改數組的長度,因此您必須將結果放在數組 nums 的前半部分。更正式地說,如果刪除重複項後有 k 個元素,則 nums 的前 k 個元素應持有最終結果。除了前 k 個元素之外,留下什麼都不重要。

將最終結果放入 nums 的前 k 個插槽後返回 k值。

Example 1:

Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Stack 解法:

自己還是只能想出來蠢方法,應該刷題量還遠遠不夠吧:

class Solution {
    public int removeDuplicates(int[] nums) {
		Stack<Integer> Stack = new Stack<Integer>();
		int k = 0;
		for (int i = 0; i < nums.length; i++) {
			if (Stack.search(nums[i])==-1) {
				Stack.push(nums[i]);
				nums[k] = nums[i];
				k++;
			} 
		}
		return k;
	}
}

7 ms

利用順序的取巧方法:

class Solution {
    public int removeDuplicates(int[] nums) {
        int i = 0;
        for(int n: nums){
            if(i == 0 || n > nums[i - 1]){
                nums[i] = n;
                i++;
            }
        }
        return i;
    }
}

1 ms

Leave a Reply

Your email address will not be published.