В очередной раз "Runtime: 0 ms, faster than 100.00% of Java online submissions" на LeetCode
В очередной раз я получил "Runtime: 0 ms, faster than 100.00% of Java online submissions", то есть "Время выполнения - 0 миллисекунд, быстрее, чем все остальные решения на Java". Так не бывает, конечно, грейдер LeetCode тупанул. Но всё-таки массивы и алгоритмы с линейным временем выполнения рулят!
Это задача https://leetcode.com/problems/remove-element/
Дан массив целых чисел nums и целое число val, удалите все вхождения val в nums без использования дополинтельной памяти (без использования дополнительного массива, разрешается использовать О(1) дополнительной памяти). Относительный порядок элементов может быть изменен.
Поскольку на некоторых языках программирования невозможно изменить длину массива, вы должны поместить результат в голову массива. Более формально, если после удаления всех вхождений val остается k элементов, то первые k элементов массива nums должны содержать результат. Неважно, что вы оставите за пределами первых k элементов.
После помещения окончательного результата в первые k слотов с числами ваша функция должна вернуть число к.
Еще раз: не выделяйте дополнительное место для другого массива. Вы должны сделать это, изменив исходный массив, разрешается использовать дополнительную память не больше O(1).
Ограничения:
На входе: nums = [3,2,2,3], val = 3 На выходе: 2, nums = [2,2,_,_] Объяснение: Ваша функция должна вернуть k = 2, послее ее работы первые два элемента массива должны быть 2. Не имеет значения, что останется после первых k элементов (поэтому там и подчеркивания).
На входе: nums = [0,1,2,2,3,0,4,2], val = 2 На выходе: 5, nums = [0,1,4,0,3,_,_,_] Объяснение: Ваша функция должна вернуть k = 5, первые 5 элементов массива должны быть 0, 0, 1, 3, и 4. Обратите внимание, что эти 5 элементов могут быть в любом порядке. Не имеет значения, что останется после первых k элементов (поэтому там и подчеркивания).
class Solution {
public int removeElement(int[] nums, int val) {
final int n = nums.length;
if (n == 0) {
return 0;
}
//first pass - val count
int valCount = 0;
for(int i =0; i < n; ++i) {
if (nums[i] == val) {
++valCount;
}
}
//second pass - replace
int readerIndex = n - valCount;
for(int i = 0; i < n - valCount; ++i) {
if (nums[i] == val) {
while(nums[readerIndex] == val) {
++readerIndex;
}
nums[i] = nums[readerIndex++];
}
}
return n - valCount;
}
}