27. Remove Element

Given an array and a value, remove all instances of that value in place and return the new length.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

27. Удаление элемента

Задан массив целых чисел и число. Удалите все вхождения этого числа не используя дополнительную память и верните новую длину массива.

Порядок элементов в массиве может меняться. Не важно какие данные останутся за новой длиной.

class Solution {

public:

int removeElement(vector<int>& nums, int val) {

}

};

РЕШЕНИЕ

последовательности

Анализ алгоритма

Заведем два индекса: i бежит по числам массива, j указывает на последний сохраненный элемент. Если nums[i] = val, то двигаем i вперед. Если nums[i] ≠ val, то устанавливаем nums[j] = nums[i] и двигаем вперед оба указателя на одну позицию.

Реализация алгоритма

class Solution

{

public:

int removeElement(vector<int>& nums, int val)

{

int i, j = 0;

for(i = 0; i < nums.size(); i++)

{

if(nums[i] == val) continue;

nums[j++] = nums[i];

}

return j;

}

};

Реализация с изменением длины массива

#include <cstdio>

#include <vector>

using namespace std;

class Solution

{

public:

int removeElement(vector<int>& nums, int val)

{

int i, j = 0;

for(i = 0; i < nums.size(); i++)

{

if(nums[i] == val) continue;

nums[j++] = nums[i];

}

nums.resize(j);

return j;

}

};

Solution s;

int main(void)

{

int m[] = {1,6,3,4,5,6,7,6,9,10};

vector<int> v(m,m+10);

int res = s.removeElement(v,6);

for(int i = 0; i < v.size(); i++)

printf("%d ",v[i]);

printf("\n");

return 0;

}