Интересный вопрос по алгоритму собеседования

опрос

Первая статья нового года, желаю всем счастливого нового года! ! Затем перейдите к тексту.

предисловие

По прихоти некоторое время назад я внезапно начал чистить leetcode. Среди них я наткнулся на интересный вопрос, который мне однажды задали интервьюеры Tencent, когда я занимался набором персонала осенью. Так поделись со всеми.

Описание темы

учитываяне пустойМассив целых чисел, в котором каждый элемент встречается дважды, кроме одного, который встречается только один раз. Найдите элемент, который встречается только один раз.

предварительное решение

На первый взгляд, идея этого вопроса довольно проста, нам нужно только поддерживать объект для записи количества вхождений каждого элемента, использовать значение элемента в качестве ключа и количество вхождений элемента как значение. Затем обойдите объект и найдите ключ, значение которого равно 1. Соответствующий ключ является этим элементом. код показывает, как показано ниже:

function singleNumber(nums) {
  const obj = {};
  for (let i = 0; i < nums.length; i++) {
    obj[nums[i]] = obj[nums[i]] ? obj[nums[i]] + 1 : 1;
  }
  for (let key in obj) {
    if (obj[key] === 1) {
      return Number(key); // 由于 key 是 string ,因此我们这里需要转化下
    }
  }
}

console.log(singleNumber([2, 2, 1, 4, 4, 5, 5, 1, 8])); // 8

увеличить лимит

Да, вопрос простой, так почему я говорю, что он интересный? Потому что на самом деле в названии есть ограничение:

Ваш алгоритм должен иметь линейную временную сложность. Можете ли вы сделать это, не используя дополнительное пространство?

Дело в томНе использует дополнительное пространство. Приведенное выше решение, создающее новый объект для хранения результата, очевидно, неосуществимо. Итак, есть ли способ реализовать эту функцию, используя только исходный массив?

окончательное решение

Мы можем подумать об этом, в массиве все числа встречаются дважды, за исключением того, который мы ищем, который появляется только один раз. Итак, есть ли способ отфильтровать два одинаковых числа?

Ну не будем об этом.Те,кто знал это раньше,должны знать решение.Если люди,которые не знали этого раньше,могут продолжить читать.

Решение: операция XOR

Операция XOR предназначена для двоичных чисел. Например, есть два двоичных числа a и b в одном. Если два значения a и b не совпадают, результат XOR равен 1. Если значения a и b совпадают, результат XOR равен 0.

А побитовая операция XOR (то есть операция ^) в javascript будет выполнять операцию XOR для каждой пары битов, соответствующих двум числам.

Например, 1 ^ 2, что по сути является операцией XOR для каждой пары битов 1 и 2, что эквивалентно следующему

  00000000000000000000000000000001 // 数字1对应的二进制
^ 00000000000000000000000000000010 // 数字2对应的二进制
= 00000000000000000000000000000011 // 数字3对应的二进制

Таким образом, результат 1 ^ 2 равен 3.

Тогда, если два одинаковых числа объединить XOR, результат можно представить, ответ будет 0.

Что, если это 0 XOR с любым числом? Результатом является само число.

В таком случае, есть ли у нас решение этой проблемы? Нам просто нужно перебрать массив, выполнить операцию XOR для всех значений, и, наконец, оставшееся значение — это число, которое появляется только один раз.
Возьмем каштан:
Предположим, у нас есть массив с элементами [a, a, c, c, b, b, d]. Затем выполняем побитовую операцию XOR над всеми элементами массива, то есть a^a^c^c^b^b^d, эквивалентна ли она 0^0^0^d=d. А d — это элемент, который появляется в массиве только один раз.
Затем мы можем расширить, для любого массива, который удовлетворяет определенному элементу, который появляется только один раз, а каждый другой элемент появляется дважды, можно ли таким образом получить элемент, который появляется только один раз.

Окончательный код выглядит следующим образом:

/**
 * 只存在一次的数字
 * https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/1/array/25/
 * @param {number[]} nums
 * @return {number}
 */
function singleNumber(nums) {
  for (let i = 1; i < nums.length; i++) {
    nums[0] ^= nums[i];
  }
  return nums[0];
};

console.log(singleNumber([2, 2, 1, 4, 4, 5, 5, 1, 8]));

Эпилог

Этот вопрос интервью в основном проверяет понимание интервьюируемым XOR, а также возможность его изучения и использования, чтобы связать этот вопрос с XOR. Конечно, самое главное — больше учиться, писать больше вопросов и читать больше книг. Вот как вы можете продолжать прогрессировать.

Адрес этой статьи находится по адресу ->Адрес моего блога, добро пожаловать, чтобы начать или подписаться

Категории