3

Vi muitas questões mostrando como pegar valores únicos em um array, mas nenhuma resolveu meu problema. Recebo um array, como este:

[ 1, 1, 1, 2, 1, 1 ]

Quero determinar o valor único dentro dele, que, nesse caso, é: 2.

Tenho um código que resolve o problema com valores pequenos, mas, com valores muito grandes, ele falha.

Segue o código:

function findUniq(arr) {
  var result;
  arr.forEach((value, index, self) => {
    var lengthAll = []; 
    self.map(x => {
      if(x === value) {
        lengthAll.push(x);
      }
    })
    if (lengthAll.length === 1) {
      result = lengthAll[0];
    }
  });
  return result;
}

Como melhorar o desempenho com valores grandes?

6
  • 2
    E se tiver dois valores únicos? Por exemplo, em: [1, 1, 2, 3]? Commented 31/05/2021 às 19:31
  • No meu problema, sempre tem um único valor diferente. Commented 31/05/2021 às 19:34
  • "mas, com valores muito grandes, ele falha" - qual é a falha?
    – vinicius
    Commented 31/05/2021 às 19:40
  • 1
    @ViniBrasil, a falha é o tempo excessivamente longo, que ocorre algoritmos quadráticos que performam sobre um número grande de elementos. Se tiver 1e5 elementos, serão feitas 1e10 iterações, o que é um absurdo e demoraria bem mais do que precisa para esse tipo de problema. Commented 31/05/2021 às 20:19
  • 1
    A noite eu publico uma resposta, mas por ora os testes de carga estão aqui: jsbench.me/awkpdlrj0d Commented 1/06/2021 às 15:50

2 Respostas 2

5

Acho que você está complicando bastante utilizando o Array.prototype.map aí. Você não precisa, de fato, de mapear o array para resolver esse problema. Parece que você está utilizando o Array.prototype.map como um substituto de Array.prototype.forEach, o que é um uso impreciso.

Além disso, a solução proposta na pergunta tem complexidade de tempo quadrática, o que significa que, para cada elemento do array, uma varredura completa será feita. Por exemplo, para um array de 100 elementos, 1002 iterações serão performadas.

Para saber mais sobre esse tipo de medida, veja Definição da notação “Big O”.


Até onde entendo, não há como resolver esse problema com menos que O(n).

Isso significa que, para um array qualquer, você deve, necessariamente, percorrer cada elemento para verificar se há algum membro garantidamente único.

Resolvendo com um mapa e somente uma varredura para cada elemento do array original, tem-se algo como:

function findUniqueElement(arr) {
  const map = new Map();

  for (const el of arr) {
    // Para cada elemento do array original, criamos um
    // registro no mapa `map` para determinar sua frequência:
    map.set(el, (map.get(el) || 0) + 1);
  }

  // Para cada elemento (sem repetição) do mapa, verificaremos
  // e retornaremos o primeiro único encontrado:
  for (const [entry, count] of map.entries()) {
    if (count === 1) return entry;
  }

  return undefined;
}

console.log(findUniqueElement([1, 1, 2, 2, 3, 3, 4])); //=> 4
console.log(findUniqueElement([1, 1, 2, 2, 3, 4])); //=> 3 (somente o primeiro único é retornado)
console.log(findUniqueElement([1, 1, 2, 2, 3, 3])); //=> undefined

A complexidade do algoritmo acima aproxima-se O(2n) (considerado linear), o que é bem melhor que O(n2) (quadrática).

Vale lembrar que essa solução retorna somente o primeiro elemento único encontrado. Se a ocorrência de mais um valor único for possível, uma alternativa é retornar um array:

function findUniqueElements(arr) {
  const map = new Map();

  for (const el of arr) {
    map.set(el, (map.get(el) || 0) + 1);
  }

  const uniqueElements = [];
  for (const [entry, count] of map.entries()) {
    if (count === 1) uniqueElements.push(entry);
  }
  return uniqueElements;
}

console.log(findUniqueElements([1, 1, 2, 2, 3, 4])); //=> [3, 4]
console.log(findUniqueElements([1, 1, 2, 2, 3, 3])); //=> []

0

Essa função retorna o primeiro valor único no array, e retorna null caso nenhum seja único.

function findUniq(arr) {
  let uniq = {};

  //Para cada elemento do array é criado um index no objeto 'uniq' e incrementado a quantidade de vezes que esse elemento aparece.
  arr.forEach(a => uniq[a] = uniq[a] ? uniq[a] + 1 : 1);
  
  //Com o objeto de contagem pronto, é possivel iterá-lo até encontrar o primeiro elemento que possui apenas uma recorrência
  for (i in uniq)
    if (uniq[i] === 1)
      return i

  //caso nenhum elemento possua apenas uma recorrência, um valor nulo é retornado
  return null;
}

console.log(findUniq([1, 1, 1, 2, 1, 1]))

1
  • 3
    Seria legal adicionar uma explicação de como o algoritmo funciona. Agregaria valor a resposta. Commented 1/06/2021 às 5:04

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .