[LeetCode] 26. Remove Duplicates from Sorted Array

Easy
Related Topics: Array / Two Pointers
LeetCode Source

解题想法

这题有 Hint 我有看一下 XD
又是 Two pointer 的问题

这里我透过一个资料结构 bag 来储存唯一的数字，但不符何题目所说的 in-place :(

演算法大致是透过寻访所有值确认实际上有哪些值被存在 nums
如果发现没有在 bag 里头则，用 bag 储存
并将 index 指向的元素替换成 i 指向的元素

Python

class Solution:    def removeDuplicates(self, nums: List[int]) -> int:        bag = []        index = 0        for i in range(len(nums)):            if nums[i] not in bag:                bag.append(nums[i])                nums[index] = nums[i]                index += 1        return index

C++

class Solution {public:    int removeDuplicates(vector<int>& nums) {        int index = 0;        vector<int> bag;        for (int i = 0; i < nums.size(); i++) {            if (std::find(bag.begin(), bag.end(), nums[i]) == bag.end()) {                bag.push_back(nums[i]);                nums[index] = nums[i];                index += 1;            }        }        return index;    }};

这里有透过 C++ 的 standard library 中的 std::find

大致上是跟 Python 中 in 中的功能很像
如果没有找到 vector 中的元素，则会回传寻访到的最后一个元素
这里是回传 vector 中的 bag.end()

附上二月多写的版本，当时演算法效率比上面的好

解题想法

由于 1 <= nums.length <= 3 * 104，所以可以从第二个项目开始看
这里我们一样有两个 pointer

不过重点是寻访判断重複值的演算法
藉由比较右边一位值的相同是否来判断是否有出现不同值
但也要记得 for loop 的边界要减一

如果发现右边出现不同值
则将 res 的值替换成 i+1
且 res += 1

Python

class Solution:    def removeDuplicates(self, nums: List[int]) -> int:        res = 1        for i in range(len(nums) - 1):            if nums[i] != nums[i+1]:                nums[res] = nums[i+1]                res += 1        return res

C++

class Solution {public:    int removeDuplicates(vector<int>& nums) {        int res = 1;        for (int i = 0; i < nums.size() - 1; i++) {            if (nums[i] != nums[i+1]) {                nums[res] = nums[i+1];                res += 1;            }        }        return res;    }};

这系列文被记录在 Top Interview 150 Series