{"id":4130,"date":"2018-10-02T09:33:53","date_gmt":"2018-10-02T16:33:53","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4130"},"modified":"2018-10-02T13:17:05","modified_gmt":"2018-10-02T20:17:05","slug":"leetcode-26-remove-duplicates-from-sorted-array","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/array\/leetcode-26-remove-duplicates-from-sorted-array\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 26. Remove Duplicates from Sorted Array"},"content":{"rendered":"

Problem<\/strong><\/h1>\n

Given a sorted array\u00a0nums<\/em>, remove the duplicates\u00a0in-place<\/strong><\/a>\u00a0such that each element appear only\u00a0once<\/em>\u00a0and return the new length.<\/p>\n

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

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

Given nums<\/em> = [1,1,2]<\/strong>,\r\n\r\nYour function should return length = 2<\/code><\/strong>, with the first two elements of nums<\/code><\/em> being 1<\/code><\/strong> and 2<\/code><\/strong> respectively. It doesn't matter what you leave beyond the returned length.<\/pre>\n
Example 2:<\/strong><\/p>\n
Given nums<\/em> = [0,0,1,1,1,2,2,3,3,4]<\/strong>,\r\n\r\nYour function should return length = 5<\/code><\/strong>, with the first five elements of nums<\/code><\/em> being modified to\u00a00<\/code><\/strong>, 1<\/code><\/strong>, 2<\/code><\/strong>, 3<\/code><\/strong>, and\u00a04<\/code><\/strong> respectively. It doesn't matter what values are set beyond\u00a0the returned length.<\/pre>\n
Clarification:<\/strong><\/p>\n
Confused why the returned value is an integer but your answer is an array?<\/p>\n
Note that the input array is passed in by\u00a0reference<\/strong>, which means modification to the input array will be known to the caller as well.<\/p>\n
Internally you can think of this:<\/p>\n
\/\/ nums<\/strong> is passed in by reference. (i.e., without making a copy)\r\nint len = removeDuplicates(nums);\r\n\r\n\/\/ any modification to nums<\/strong> in your function would be known by the caller.\r\n\/\/ using the length returned by your function, it prints the first len<\/strong> elements.\r\nfor (int i = 0; i < len; i++) {\r\n\u00a0 \u00a0 print(nums[i]);\r\n}<\/pre>\n
Solution:<\/h1>\n
Time complexity: O(n)<\/p>\n
Space complexity: O(1)<\/p>\n
\n
C++<\/h2>\n
\n\n
\/\/ Author: Huahua\r\nclass Solution {\r\npublic:\r\n  int removeDuplicates(vector<int>& nums) {\r\n    const int n = nums.size();\r\n    if (n <= 1) return n;        \r\n    int ans = 0;\r\n    int i = 0;\r\n    while (i < n) {\r\n      nums[ans++] = nums[i];\r\n      int j = i + 1;\r\n      while (j < n && nums[j] == nums[j - 1]) ++j;\r\n      i = j;\r\n    }\r\n    return ans;\r\n  }\r\n};<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
Problem Given a sorted array\u00a0nums, remove the duplicates\u00a0in-place\u00a0such that each element appear only\u00a0once\u00a0and return the new length. Do not allocate extra space for another array,…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[184],"tags":[20,21,222,252,23],"class_list":["post-4130","post","type-post","status-publish","format-standard","hentry","category-array","tag-array","tag-deduplication","tag-easy","tag-remove","tag-sort","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4130","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=4130"}],"version-history":[{"count":6,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4130\/revisions"}],"predecessor-version":[{"id":4145,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4130\/revisions\/4145"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4130"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4130"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4130"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}