{"id":4135,"date":"2018-10-02T12:32:20","date_gmt":"2018-10-02T19:32:20","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4135"},"modified":"2018-10-02T12:32:37","modified_gmt":"2018-10-02T19:32:37","slug":"leetcode-27-remove-element","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/array\/leetcode-27-remove-element\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 27. Remove Element"},"content":{"rendered":"

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

Given an array\u00a0nums<\/em>\u00a0and a value\u00a0val<\/em>, remove all instances of that value\u00a0in-place<\/strong><\/a>\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

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.<\/p>\n

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

Given nums<\/em> = [3,2,2,3]<\/strong>, val<\/em> = 3<\/strong>,\r\n\r\nYour function should return length = 2<\/strong>, with the first two elements of nums<\/em> being 2<\/strong>.\r\n\r\nIt doesn't matter what you leave beyond the returned length.\r\n<\/pre>\n
Example 2:<\/strong><\/p>\n
Given nums<\/em> = [0,1,2,2,3,0,4,2]<\/strong>, val<\/em> = 2<\/strong>,\r\n\r\nYour function should return length = 5<\/code><\/strong>, with the first five elements of nums<\/code><\/em> containing\u00a00<\/code><\/strong>, 1<\/code><\/strong>, 3<\/code><\/strong>, 0<\/code><\/strong>, and\u00a04<\/strong>. Note that the order of those five elements can be arbitrary. 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 = removeElement(nums, val);\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:<\/strong><\/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 removeElement(vector<int>& nums, int val) {\r\n    int len = 0;\r\n    for (int num : nums)\r\n      if (num != val) nums[len++] = num;\r\n    return len;\r\n  }\r\n};<\/pre>\n\n<\/div>
Python3<\/h2>\n
\n\n
class Solution:\r\n  def removeElement(self, nums, val):\r\n    l = 0\r\n    for num in nums:\r\n      if num != val:\r\n        nums[l], l = num, l + 1        \r\n    return l<\/pre>\n<\/div><\/div>\n
Related Problems<\/strong><\/h1>\n