Серия алгоритмических задач «Нахождение числа, которое встречается только один раз»

алгоритм

В настоящее время в серии «поиск чисел, встречающихся только один раз» есть три основные алгоритмические задачи:

  • Вопрос 1: Только один элемент в массиве встречается только один раз, а остальные элементы встречаются дважды Найдите этот элемент;
  • Вопрос 2: Только два элемента в массиве встречаются только один раз, а остальные элементы встречаются дважды Найдите этот элемент;
  • Тема вторая: только один элемент в массиве встречается только один раз, остальные элементы встречаются трижды, ища этот элемент;

Такие алгоритмы тематические решения следующие:

Вариант 1. Подсчитайте количество вхождений каждого числа

Создайте карту (ключ — это элемент в массиве, а значение — количество раз, которое элемент появляется), просмотрите все элементы в массиве и, наконец, просмотрите карту, чтобы найти элемент, который появляется только один раз.

function singleNumber(nums = []) {
    let map = {};
    nums.forEach(num => map[num] ? map[num]++ : (map[num] = 1));
    return Object.keys(map).filter(num => map[num] === 1).map(num => parseInt(num));
}

Преимущество этого метода в том, что он относительно прост и может решить три вышеперечисленные проблемы, но объемная сложность относительно высока: если элементов массива много, карта занимает слишком много места.

Вариант 2. Подсчитайте количество вхождений каждого двоичного бита.

Поскольку число в вопросе имеет тип Int, вы можете создать массив размером 32 для подсчета количества вхождений 1 в каждой цифре.Если цифра равна 1, то, если целое число встречается три или два раза ( Посмотрите на число вхождения оставшихся элементов в вопросе), приравняйте остаток к 0 для 3 или 2 (подробности см. в вопросе), поэтому сложите соответствующие биты каждого числа, чтобы получить остаток от 3 или 2, и последний номер Индивидуальные номера:

function singleNumber(nums = []) {
    let res = 0;
    for (let i = 0; i < 32; i++) {
        let sum = 0;
        for (let j = 0; j < nums.length; j++) {
            sum += (nums[j] >> i) & 1;
        }
        res |= (sum % 2) << i;
    }
    return res;
}

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

Вариант 3: Гибкое применение битовых операций

Решение битовой операции «Проблема 1»:

Думая, что операция XOR в битовой операции может привести к тому, что результат операции XOR двух одинаковых чисел должен быть равен 0, тогда мы можем пройти весь массив и выполнить операцию XOR для всех элементов, а результат XOR для всех появившихся элементов дважды изменится. Если он станет 0, то остальное должно быть числом, которое появляется только один раз, разве это не удивительно:

function singleNumber(nums = []) {
    let res = 0;
    nums.forEach(num => res = res ^ num);
    return res;
}

Это решение имеет небольшой объем кода и наименьшую сложность времени и места.

Решение битовой операции «Проблема 2»:

Если только одно число появляется один раз, мы можем получить число напрямую с помощью XOR.Если два числа встречаются только один раз, результатом XOR должен быть результат XOR этих двух чисел, тогда мы Как его разделить? Мы можем думать, что если определенный бит этого результата равен 1 (просто найдите любой бит, который равен 1), то должно быть, что соответствующие двоичные биты в этих двух числах равны 0 и 1, тогда мы можем основываться на этом. бит делит все числа в списке на две категории, одна представляет собой список, где бит равен 0, а другая представляет собой список, где бит равен 1, тогда «Заголовок 2» разбирается на две подзадачи «Заголовок 1». " , вы также можете получить эти два числа, которые появляются только один раз:

function singleNumber(nums = []) {
    let res = 0;
    nums.forEach(num => res = res ^ num);
    let i = 0;
    while(!((res >> i) & 1)){
        i++;
    }
    let res1 = 0, res2 = 0;
    nums.forEach(num => {
        if((num >> i) & 1){
            res1 = res1 ^ num;
        }else{
            res2 = res2 ^ num;
        }
    });
    return [res1, res2];
}
Решение битовой операции «Проблема 3»:

Для «названия 3», если мы напрямую используем метод решения 1 и решение для решения проблемы, он, похоже, не работает, потому что количество раз оставшиеся элементы появляются три раза, XOR не может сделать результат оставшихся Элементы становятся 0, если хорная операция тройной, то, возможно, может, но к сожалению XOR может работать только на двоичном, так что есть ли решение для симуляции тройной работы? Ответ да.

Мы можем использовать 3 целых числа, чтобы представить, сколько раз встречается каждая единица:

  • единиц означает, что каждый бит имеет только 1 вхождение 1
  • двойки означают, что каждый бит имеет только 2 вхождения 1
  • тройки означают только 3 вхождения 1 для каждого бита
function singleNumber(nums) {
    let one = 0, two = 0, three = 0;
    for (let i = 0; i < nums.length; i++) {
        //如果最近连续两次为 1，或者原先 two 就为 1，那么 two 就为 1，two 的计算必须放在 one 前面，这里的 & 是与上一次的 one 
        two |= one & nums[i];  
        //每次通过异或更新只出现的一次的结果，和《题目一》《题目二》的类似
        one ^= nums[i];
        //如果一个位既出现了一次，也出现了两次，表示这个数字出现了3次
        three = one & two;
        //清零 one，two 中出现三次的位
        one &= ~three;
        two &= ~three;
    }
    return one;
}
Категории