[Leetcode][python]删除排序数组中的重复项/删除排序数组中的重复项 II

蔚落 2022-06-12 02:14 281阅读 0赞

# Remove Duplicates from Sorted Array #

## 题目大意 ##

对排好序的list去重，输出去重后长度，并且不能创建新的数组

## 解题思路 ##

**快慢指针**

## 代码 ##

### 官方答案 ###

数组完成排序后，我们可以放置两个指针 i 和 j，其中 i 是慢指针，而 j 是快指针。只要 nums\[i\] = nums\[j\]，我们就增加 j 以跳过重复项。

当我们遇到 nums\[j\] \\neq nums\[i\]nums\[j\]≠nums\[i\] 时，跳过重复项的运行已经结束，因此我们必须把它（nums\[j\]nums\[j\]）的值复制到 nums\[i + 1\]nums\[i+1\]。然后递增 i，接着我们将再次重复相同的过程，直到 jj 到达数组的末尾为止。

public int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;
        int i = 0;
        for (int j = 1; j < nums.length; j++) {
            if (nums[j] != nums[i]) {
                i++;
                nums[i] = nums[j];
            }
        }
        return i + 1;
    }

### 我提交的（不忍直视） ###

class Solution(object):
        def removeDuplicates(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            j = 0
            for i in range(len(nums)):
                if nums[i] == nums[j]:
                    i += 1
                    continue
                else:
                    nums[j+1] = nums[i]
                    i += 1
                    j += 1
            nums = nums[:j+1]
            return len(nums)

# Remove Duplicates from Sorted Array II #

## 题目大意 ##

在 Remove Duplicates from Sorted Array（从一个有序的数组中去除重复的数字，返回处理后的数组长度） 的基础上，可以使每个数字最多重复一次，也就是说如果某一个数字的个数大于等于2个，结果中应保留2个该数字。

## 解题思路 ##

参考：http://www.cnblogs.com/zuoyuan/p/3783453.html  
使用两个指针prev和curr，判断A\[curr\]是否和A\[prev\]、A\[prev-1\]相等，如果相等curr指针继续向后遍历，直到不相等时，将curr指针指向的值赋值给A\[prev+1\]。

## 代码 ##

class Solution(object):
        def removeDuplicates(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            if len(nums) <= 2: 
                return len(nums)
            prev = 1
            curr = 2
            while curr < len(nums):
                # print 'curr:', nums[curr], 'prev, prev-1:', nums[prev], nums[prev - 1]
                if nums[curr] == nums[prev] and nums[curr] == nums[prev - 1]:
                    curr += 1
                else:
                    prev += 1
                    # print 'fu zhi gei prev hou de yi wei:', nums[prev], nums[curr]
                    nums[prev] = nums[curr]
                    curr += 1
            return prev + 1

## 总结 ##