# 27. Remove Element
[](https://hackmd.io/-G5lZlxgRsaqV8YZAczr5w)
###### tags: `Leetcode`
Source: [:link:][leetcode link]
[leetcode link]:
https://leetcode.com/problems/remove-element/
Average Rating：:star::star::star::star:
## Question Description
:::info
Given an integer array `nums` and an integer `val`, remove all occurrences of `val` in `nums` [in-place](https://en.wikipedia.org/wiki/In-place_algorithm). The relative order of the elements may be changed.
Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the **first part** of the array `nums`. More formally, if there are k elements after removing the duplicates, then the first `k` elements of `nums` should hold the final result. It does not matter what you leave beyond the first `k` elements.
Return `k` after placing the final result in the first k slots of `nums`.
Do **not** allocate extra space for another array. You must do this by **modifying the input array** in-place with **O(1)** extra memory.
:::
***Custom Judge:***
The judge will test your solution with the following code:
```cpp
int[] nums = [...]; // Input array
int val = ...; // Value to remove
int[] expectedNums = [...]; // The expected answer with correct length.
// It is sorted with no values equaling val.
int k = removeElement(nums, val); // Calls your implementation
assert k == expectedNums.length;
sort(nums, 0, k); // Sort the first k elements of nums
for (int i = 0; i < actualLength; i++) {
assert nums[i] == expectedNums[i];
}
```
If all assertions pass, then your solution will be **accepted**.
**Example 1**
```cpp=
Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2,_,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 2.
It does not matter what you leave beyond the returned k (hence they are underscores).
```
**Example 2**
```cpp=
Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4.
Note that the five elements can be returned in any order.
It does not matter what you leave beyond the returned k (hence they are underscores).
```
**Constraints:**
* 0 <= nums.length <= 100
* 0 <= nums[i] <= 50
* 0 <= val <= 100
## Question Explanation
***English Version***
When the first time that I tried to solve this problem, I thought about to remove the elements that we don't need. But the most important and foundamental thing is:
:::danger
The elements of an array are contiguous in memory addresses and that you cannot delete an element of an array individually, and you could only **overwrite** it.
数组的元素在内存地址中是***连续*** 的，不能单独删除数组中的某个元素，只能***覆盖***
:::
And thus, when you use `for` loops and remove the items inside the loop, you will get the wrong answer.
Example:
```python=
Wrong answer1:
for item in nums:
if item == val:
nums.remove(item)
Wrong answer2:
for index, item in enumerate(nums):
if item == val:
del nums[index]
```
Please review [Arrays [Theoretical foundations]](/0uhTX3AdTeiH9elh3GiTLQ)
Since this question is asking us to remove all elements of the given value in-place, we have to handle it with `O(1)` extra space. How to solve it? We can keep two pointers `i` and `j`, where `i` is the slow-runner while `j` is the fast-runner
:pushpin:*Algorithm:*
When nums[j] equals to the given value, skip this element by incrementing jj. As long as nums[j] $\neq$ =val, we copy nums[j] to nums[i] and increment both indexes at the same time. Repeat the process until j reaches the end of the array and the new length is i.
:::success
通过一个快指针和慢指针在一个for循环下完成两个for循环的工作
:::
:pushpin:*Consider to use Brute Force:*
Use two loops. One iterates through the elements of the array, and the second updates the array
```python=
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
i = 0
n = len(nums)
while i < n:
if nums[i] == val:
j = i + 1
while j < n:
nums[j-1] = nums[j]
n = n -1
return n
```
## Code
Python (36 ms)
```python=
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
while val in nums:
nums.remove(val)
return len(nums)
```
But This method still needs to iterate through the entire array
Python (24 ms)
```python=
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
i,n = 0,len(nums)
for j in range(n):
if nums[j] != val:
nums[i] = nums[j]
i += 1
return i
```
:::success
Python (28 ms)
```python=
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
left, right = 0, 0
while right < len(nums):
if nums[right] != val:
nums[left] = nums[right]
left += 1
right += 1
return left
```
The most easier one to be understood
>双指针 每次fast runner向右移动一步 如果!=val 则使用slow runner来讲要保留的array更新 **保证slow runner每走一步 都是在记录不重复的value 最后得到的left runner的值 即为不重复的value的个数**
:::
## Linked Questions
* 26.删除排序数组中的重复项
* 283.移动零
* 844.比较含退格的字符串
* [977. Squares of a Sorted Array](/tGWc1byfTwy_anosvUftsg)
## Q&A
N/A
Sign in with Wallet
Connect another wallet