LeetCode 80 Remove Duplicates from Sorted Array II

简介: 给定排序的数组nums,就地删除重复项,使重复项最多出现两次并返回新的长度.不要为另一个数组分配额外的空间,必须通过使用O(1)复杂度的额外空间来修改输入数组,从而实现此目的.

v2-ae1864ee17942afd4a03ca79d08f8494_1440w.jpg

Description



Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length.


Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.


Example 1:


Given nums = [1,1,1,2,2,3],

Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively.

It doesn't matter what you leave beyond the returned length.


Example 2:


Given nums = [0,0,1,1,1,1,2,3,3],

Your function should return length = 7, with the first seven elements of nums being modified to 0, 0, 1, 1, 2, 3 and 3 respectively.

It doesn't matter what values are set beyond the returned length.


Clarification:


Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.


Internally you can think of this:


// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);
// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
print(nums[i]);
}


描述



给定排序的数组nums,就地删除重复项,使重复项最多出现两次并返回新的长度.

不要为另一个数组分配额外的空间,必须通过使用O(1)复杂度的额外空间来修改输入数组,从而实现此目的.


例1:给定nums = [1,1,1,2,2,3],函数应返回length = 5,其中nums的前五个元素分别为1,1,2,2和3.


数组中超出了你返回范围的值无关紧要.


例2:给定nums = [0,0,1,1,1,1,2,3,3],函数应返回length = 7,nums的前七个元素分别修改为0,0,1,1,2,3和3。


数组中超出了你返回范围的值无关紧要.


对为什么返回值是一个整数但输出的答案是一个数组感到迷惑?


请注意,输入数组通过引用传入,这意味着调用者也将知道对输入数组的修改。

下面这个例子可以帮助你理解:


// nums通过引用传入。 (即没有复制)
int len = removeDuplicates(nums);
//调用者可以知道函数中对nums的任何修改。
//使用函数返回的长度,打印出前len个元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}


思路



  • 这道题我们采用就地移动的方式来是空间复杂度达到O(1).
  • 我们两个变量index,count:index表示已经到达最终位置的元素的后面一个值,count表示当前元素出现的次数.
  • index和count都初始化为1.
  • 如果当前元素等于前面一个元素,count自增一次,如果不等count重置为1.
  • 如果count小于等于2,我们把当前元素放到nums[index],index自增一次.
  • 直到遍历到nums尾部,我们返回index.


# -*- coding: utf-8 -*-
# @Author:             何睿
# @Create Date:        2018-12-22 17:55:43
# @Last Modified by:   何睿
# @Last Modified time: 2018-12-23 10:35:05
class Solution:
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # 如果是空则返回0
        if not nums:
            return 0
        index, count = 1, 1
        for i in range(1, len(nums)):
            # 如果两个字符相等
            if nums[i-1] == nums[i]:
                # count计数自增一次
                count += 1
            # 如果不等,count重置为1
            else:
                count = 1
            # 如果count小于等于2,则把nums[i]放到有效位置的后一个位置
            if count <= 2:
                nums[index] = nums[i]
                index += 1
        # 删除无用元素[也可不用删除,LeetCode不会检查后面的元素]
        del nums[index:]
        return index
if __name__ == "__main__":
    nums = [0, 0, 1, 1, 1, 1, 2, 3, 3]
    so = Solution()
    res = so.removeDuplicates(nums)
    print(res, nums)


源代码文件在这里.


目录
相关文章
Leetcode 4. Median of Two Sorted Arrays
题目描述很简单,就是找到两个有序数组合并后的中位数,要求时间复杂度O(log (m+n))。 如果不要去时间复杂度,很容易就想到了归并排序,归并排序的时间复杂度是O(m+n),空间复杂度也是O(m+n),不满足题目要求,其实我开始也不知道怎么做,后来看了别人的博客才知道有个二分法求两个有序数组中第k大数的方法。
39 0
Leetcode Find Minimum in Rotated Sorted Array 题解
对一个有序数组翻转, 就是随机取前K个数,移动到数组的后面,然后让你找出最小的那个数,注意,K有可能是0,也就是没有翻转。
49 0
Search in Rotated Sorted Array - 循环有序数组查找问题
Search in Rotated Sorted Array - 循环有序数组查找问题
70 0
LeetCode 167 Two Sum II - Input array is sorted(输入已排序数组,求其中两个数的和等于给定的数)
给定一个有序数组和一个目标值 找出数组中两个成员,两者之和为目标值,并顺序输出
88 0
LeetCode contest 200 5476. 找出数组游戏的赢家 Find the Winner of an Array Game
LeetCode contest 200 5476. 找出数组游戏的赢家 Find the Winner of an Array Game
|
算法 Python
LeetCode 108. 将有序数组转换为二叉搜索树 Convert Sorted Array to Binary Search Tree
LeetCode 108. 将有序数组转换为二叉搜索树 Convert Sorted Array to Binary Search Tree
|
算法 测试技术
LeetCode 88. 合并两个有序数组 Merge Sorted Array
LeetCode 88. 合并两个有序数组 Merge Sorted Array
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
57 6
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
114 2