# Remove Element of Array series

## 1. Requirements

Given an array and a value, remove all instances of that > value in place and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
The order of elements can be changed. It doesn't matter what you leave beyond the new length.

Example:
Given input array nums = [3,2,2,3], val = 3
Your function should return length = 2, with the first two elements of nums being 2.

## 2. The first way

Idea: traverse all items of vector and compare with val respectively
*Same: index is not added, nums[i] is assigned to nums[index]
*Different: index plus 1, no assignment required

```#include <iostream>
#include <vector>
using namespace std;```

### 2.2 implementation code

```/*
Idea: traverse all items of vector and compare with val respectively
Same: index is not added, nums[i] is assigned to nums[index]
Different: index plus 1, no assignment required
Time complexity O(n), space complexity O(1)
*/
class Solution
{
public:
int removeElement(vector<int>& nums, int val)
{
int index = 0;
for (size_t i = 0; i < nums.size(); ++i)
{
if (nums[i] != val)
nums[index++] = nums[i];
}

return index;
}
};```

### 2.3 test code

```int main()
{
using namespace std;
Solution sol;
vector<int> vec{1, 2, 5, 6, 12, 45, 8, 4, 5, 4};
cout << "Original vector's size is " << vec.size() << endl;

int count = sol.removeElement(vec, 5);

cout << "New vector's size is " << count << endl;
for (int i = 0; i < count; ++i)
cout << "vec[" << i << "] = " << vec[i] << endl;

return 0;
}```

## 3. The second way

Idea: use remove and distance functions to realize.
Reference from: https://github.com/soulmachine/leetcode
Introduction to remove MSDN
remove blog reference
Introduction to distance MSDN

### 3.1 remove()

#### 3.1.1 grammar

```template<class ForwardIterator, class T>
ForwardIterator remove(ForwardIterator first, ForwardIterator last,
const T& value);```

#### 3.1.2 parameters

• _First
An iterator that addresses the location of the first element in the scope of the element to be removed.
• _Last
An iterator that addresses the next location of the last element in the scope of the element to be removed.
• _Val
The value to remove from the range.

#### 3.1.3 return value

An iterator that points to the last next "undeleted" element. The return value is the "new logical end point" of the interval.

#### 3.1.4 attention

The role of remove in vector is to put the element equal to value at the end of vector, but it does not reduce the size of vector

### 3.2 distance()

#### 3.2.1 grammar

```template<class InputIterator>
typename iterator_traits<InputIterator>::difference_type
distance(
InputIterator _First,
InputIterator _Last
);```

#### 3.2.2 parameters

• _First

To calculate the starting point of the distance iterator.

• _Last
To calculate the end of the distance iterator.

#### 3.2.3 return value

The number of elements between First and Last.

#### 3.2.3 requirements

```Header: <iterator>
Namespace: std```

### 3.3 header documents and preparations

```#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;```

### 3.4 implementation code

```/*
Idea: using distance and remove functions
Time complexity O(n), space complexity O(1)
*/
class Solution2
{
public:
int removeElement(vector<int>& nums, int val)
{
return distance(nums.begin(), remove(nums.begin(), nums.end(), val));
}
};```

### 3.5 test code

```vector<int> vec2{3,2,2,3};
int count = sol2.removeElement(vec2, 3);
cout << "New vector2's size is " << count << endl;
cout << "New vector2's real size is " << vec2.size();
for (int i = 0; i < count; ++i)
cout << "vec[" << i << "] = " << vec2[i] << endl;```

## 4. Full code

The complete code can be found in GitHub .

Tags: github

Posted on Thu, 30 Apr 2020 18:25:05 -0700 by kristinac