{"id":5669,"date":"2019-09-30T23:30:11","date_gmt":"2019-10-01T06:30:11","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5669"},"modified":"2019-09-30T23:30:54","modified_gmt":"2019-10-01T06:30:54","slug":"leetcode-80-remove-duplicates-from-sorted-array-ii","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/array\/leetcode-80-remove-duplicates-from-sorted-array-ii\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 80. Remove Duplicates from Sorted Array II"},"content":{"rendered":"\n

Given a sorted array nums<\/em>, remove the duplicates in-place<\/strong><\/a> such that duplicates appeared at most twice<\/em> and return the new length.<\/p>\n\n\n\n

Do not allocate extra space for another array, you must do this by modifying the input array in-place<\/a><\/strong> with O(1) extra memory.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Given nums<\/em> = [1,1,1,2,2,3]<\/strong>,\n\nYour function should return length = 5<\/code><\/strong>, with the first five elements of nums<\/code><\/em> being 1, 1, 2, 2<\/code><\/strong> and 3<\/strong> respectively.\n\nIt doesn't matter what you leave beyond the returned length.<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Given nums<\/em> = [0,0,1,1,1,1,2,3,3]<\/strong>,\n\nYour function should return length = 7<\/code><\/strong>, with the first seven elements of nums<\/code><\/em> being modified to 0<\/code><\/strong>, 0<\/strong>, 1<\/strong>, 1<\/strong>, 2<\/strong>, 3<\/strong> and 3<\/strong> respectively.\n\nIt doesn't matter what values are set beyond the returned length.<\/pre>\n\n\n\n
Solution:<\/strong><\/h2>\n\n\n\n
Time complexity: O(n)
Space complexity: O(1)<\/p>\n\n\n\n
\n
C++<\/h2>\n
\n\n
\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int removeDuplicates(vector& nums) {\n    const int n = nums.size();\n    if (n <= 2) return n;\n\n    int index = 1;\n    int len = 1;\n    int last = nums[0];\n\n    while (index < n) {\n      int count = 1;\n      while (index < n && nums[index] == last) {\n        ++count;\n        ++index;\n      }\n\n      if (count >= 2) nums[len++] = last;        \n\n      if (index < n) {\n        last = nums[index++];\n        nums[len++] = last;\n      }\n    }\n\n    return len;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n
Related Problems<\/strong><\/h2>\n\n\n\n