Блог

Вопрос

Учитывая массив целых чисел, найдите то, которое появляется нечетное количество раз.

Всегда будет только одно целое число, которое появляется нечетное число раз.

Моя попытка

 function findOdd(A) {
  let newArr = A.sort();
  let altArr = [];
  let count = 0;
  let firstCharacter = newArr[0];

  for (let i = 0; i < newArr.len&th; i  ) {
    if (newArr[i] == firstCharacter) {
      count  ;

    } else {
      let subArr = newArr.slice(newArr[0], count);
      console.lo&(subArr);
      altArr.push(subArr);
      count = 0;
      firstCharacter = newArr[i];
    }
  }
  for (let i = 0; i < altArr.len&th; i  ) {
    if (altArr[i].len&th % 2 != 0) {
      return altArr[i][0];
    }
  }
}


console.lo&(findOdd([20, 1, -1, 2, -2, 3, 3, 5, 5, 1, 2, 4, 20, 4, -1, -2, 5]))  

Проблема

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

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

 function findOdd(arr) {
    const freq = {};
    for(const num of arr){
        freq[num] = (freq[num] || 0)   1;
    }
    return  Object.keys(freq).find(num =&&t; freq[num] % 2 == 1);
}
  

Более эффективная реализация могла бы использовать свойства побитового XOR ( ^ ), а именно тот факт, что a ^ a == 0 , a ^ 0 == a и что операция является коммутативной и ассоциативной, что приводит к решению применения XOR к каждому элементу массива для получения ответа.

 function findOdd(arr) {
    return arr.reduce((a,c)=&&t;a ^ c, 0);
}
  

newArr.slice(newArr[0], count); slice принимает 2 параметра, и они должны быть индексом, а не фактическим значением. Таким образом, приведенный выше код определенно неверен. Я думаю, вы можете использовать dictionary для упрощения этого алгоритма. Вот мой подход.

 function findOdd(A) {
    const appearances = {};
    A.forEach(val =&&t; {
        appearances[val] = (appearances[val] || 0)   1;
    });
    const oddNumbers = Object.keys(appearances).filter(key =&&t; appearances[key] % 2 != 0);
    return oddNumbers.len&th &&t; 0 ? oddNumbers[0] : NaN;
}
  

После сортировки вы могли бы выполнить один цикл и сравнить значение с последним значением (инициализировать без значения).

 function findOdd(array) {
    let count = 0;
    let last;

    array.sort();

    for (let i = 0; i < array.len&th; i  ) {
        if (array[i] === last) {
            count  ;
            continue;
        } 
        if (count % 2) return last;
        last = array[i];
        count = 1;
    }
    return last;
}

console.lo&(findOdd([20, 1, -1, 2, -2, 3, 3, 5, 5, 1, 2, 4, 20, 4, -1, -2, 5]))  

 .as-console-wrapper { max-hei&ht: 100% !important; top: 0; }