Вопрос

Учитывая массив целых чисел nums длины n, где все целые числа nums находятся в диапазоне [1, n], и каждое целое число встречается один раз или дважды, вернуть массив всех целые числа, которые появляются дважды.

Вы должны написать алгоритм, который работает за O(n) времени и использует только постоянное дополнительное пространство.

Пример 1:

Ввод: число = [4,3,2,7,8,2,3,1]

Вывод: [2,3]

Пример 2:

Ввод: число = [1,1,2]

Вывод: [1]

Пример 3:

Ввод: число = [1]

Вывод: []

Ограничения:

  • n == nums.length
  • 1 <= n <= 105
  • 1 <= nums[i] <= n
  • Каждый элемент в nums появляется один раз или дважды.

Решение первое

Анализ:

Используйте уникальную функцию Set, чтобы непрерывно добавлять числа в nums к пустому Set, а затем используйте метод set.add, чтобы определить, есть ли повторяющиеся числа, увеличивая длину set.

Код:

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findDuplicates = function (nums) {
  const set = new Set(); // unique value test
  const result = []; // result array
  nums.forEach((n) => {
    const preSize = set.size;
    // Use the set.add method to determine whether there are duplicate numbers by getting the length of the set to increase
    set.add(n);
    // find duplicate numbers
    if (preSize === set.size) {
      result.push(n);
    }
  });
  return result;
};

Решение второе

Анализ:

Пройдите весь массив, обработайте каждое число как информацию о позиции массива, а затем измените число, соответствующее каждой позиции, на отрицательное число, что эквивалентно созданию отметки, указывающей, что позиция, соответствующая этому числу, уже занята числом. , и мы встретимся снова в следующий раз Если это число окажется отрицательным, значит, оно уже появилось.

Например, [4,3,2,7,8,2,3,1], при достижении первого 2 число 3, чья позиция 1, переворачивается на -3, переходите к следующему 2 можно найти число -3 в позиции 1, которое было перевернуто, что указывает на то, что число 2 встречается дважды .

Код:

/**
  * @param {number[]} nums
  * @return {number[]}
  */
var findDuplicates = function(nums) {
     let result = [];
     for (let i = 0; i < nums.length; i++) {
         let num = Math.abs(nums[i]);
         if (nums[num - 1] > 0) {
             /**
              The purpose of flipping the number to a negative number is to make a mark to indicate that the position corresponding to the number is already occupied by a number. If the number is found to be a negative number next time, it means that it has already appeared.
              For example [4,3,2,7,8,2,3,1]
              When you go to the first 2, the number in position 1 is 3, flip the 3 to -3, and when you go to the next 2, when you flip 3, you find that it has been flipped.
              */
             nums[num - 1] *= -1;
         } else {
             result.push(num);
         }
     }
     return result;
};

Ознакомьтесь с дополнительными примечаниями LeetCode: https://lwebapp.com/en/tag/leetcode

Ссылка