Java | LeetCode
Задача: 442. Find All Duplicates in an Array
Сложность: medium
Дан целочисленный массив nums длины n, где все целые числа nums находятся в диапазоне [1, n], и каждое число появляется один или два раза. Верните массив всех чисел, которые появляются дважды.
Вы должны написать алгоритм, который работает за время O(n) и использует только постоянное дополнительное пространство.
Пример:
Input: nums = [4,3,2,7,8,2,3,1]
Output: [2,3]
👨💻 Алгоритм:
1⃣Когда мы итерируемся по элементам входного массива, мы можем просто искать любое другое вхождение текущего элемента в оставшейся части массива.
2⃣Поскольку элемент может появляться только один или два раза, нам не нужно беспокоиться о получении дубликатов элементов, которые появляются дважды: Случай I: Если элемент встречается в массиве только один раз, при поиске его в остальной части массива ничего не найдется. Случай II: Если элемент встречается дважды, вы найдете второе вхождение элемента в оставшейся части массива. Когда вы наткнетесь на второе вхождение в более поздней итерации, это будет аналогично случаю I (поскольку больше вхождений этого элемента в оставшейся части массива не будет).
3⃣Таким образом, можно эффективно определить все элементы, которые встречаются дважды, и добавить их в результирующий массив, проходя по каждому элементу массива и проверяя наличие его второго вхождения в оставшейся части массива.
😎 Решение:
class Solution {
public List<Integer> findDuplicates(int[] nums) {
List<Integer> ans = new ArrayList<>();
for (int i = 0; i < nums.length; i++)
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] == nums[i]) {
ans.add(nums[i]);
break;
}
}
return ans;
}
}
Ставь 👍 и забирай 📚 Базу знаний
2 · 388 ·