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

2.1 header and preparation

#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;
}

2.4 operation results

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;

3.6 operation results

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