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.
Задан массив целых чисел и
число. Удалите все вхождения этого числа, не используя
дополнительную память и верните новую длину массива.
Порядок элементов в массиве
может меняться. Не важно какие данные останутся за новой длиной.
// C++
class Solution {
public:
int removeElement(vector<int>&
nums, int val) {
}
};
// Java
public class
Solution {
public int
removeElement(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;
}
Java реализация
public class Solution
{
public int
removeElement(int[] nums, int val)
{
int j = 0;
for(int i = 0; i <
nums.length; i++)
{
if(nums[i] == val) continue;
nums[j++] =
nums[i];
}
return j;
}
}