Given a sorted array,
remove the duplicates in place such that each element appear only once and
return the new length.
Do not allocate extra space
for another array, you must do this in place with constant memory.
For example, given input
array nums = [1,1,2], your function should return length = 2, with the first two elements
of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the
new length.
Задан отсортированный массив
чисел. Удалите из него все дубли – то есть каждый элемент в массиве должен
встречаться только один раз. Используйте константную память, не объявляйте
новых массивов. Верните новую длину массива.
Например, пусть входной
массив nums = [1,1,2]. Ваша функция должна вернуть length = 2, с двумя элементами в массиве:
1 и 2. Не имеет значения, что будет содержать массив за пределами новой границы.
// C++
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
}
};
// Java
public class Solution {
public int
removeDuplicates(int[] nums) {
}
}
последовательности
Заведем два индекса: j бежит по
числам массива, i указывает на
последний сохраненный элемент. Если nums[i] ≠ nums[j], то двигаем i
вперед и на место nums[i] записываем nums[j].
Реализация алгоритма
class Solution
{
public:
int removeDuplicates(vector<int>& nums)
{
if (nums.size() == 0) return
0;
int i = 0;
for(int j = 1; j <
nums.size(); j++)
if (nums[i] != nums[j])
{
i++;
nums[i] =
nums[j];
}
nums.resize(i+1);
return nums.size();
}
};
Java реализация
public class
Solution
{
public int
removeDuplicates(int[] nums)
{
if (nums.length == 0) return
0;
int i = 0;
for(int j = 1; j <
nums.length; j++)
if (nums[i] != nums[j])
{
i++;
nums[i] =
nums[j];
}
return i + 1;
}
}