Encuentra el único elemento diferente en una array

Posted on by Rudeus Greyrat

Dada una array de enteros donde todos los elementos son iguales excepto uno, encuentre el único elemento diferente en la array. Se puede suponer que el tamaño de la array es de al menos dos.
Ejemplos:
 

Entrada: arr[] = {10, 10, 10, 20, 10, 10} 
Salida: 3 
arr[3] es el único elemento diferente.
Entrada: arr[] = {30, 10, 30, 30, 30} 
Salida: 1 
arr[1] es el único elemento diferente.

Una solución simple es atravesar la array. Para cada elemento, compruebe si es diferente de los demás o no. La complejidad temporal de esta solución sería O(n*n)
Una mejor solución es usar hash. Contamos las frecuencias de todos los elementos. La tabla hash tendrá dos elementos. Imprimimos el elemento con valor (o frecuencia) igual a 1. Esta solución funciona en O(n) tiempo pero requiere O(n) espacio adicional.
Una solución eficiente es verificar primero los tres primeros elementos. Puede haber dos casos, 
 

  1. Dos elementos son iguales, es decir, uno es diferente según las condiciones dadas en la pregunta. En este caso, el elemento diferente está entre los tres primeros, por lo que devolvemos el elemento diferente.
  2. Los tres elementos son iguales. En este caso, el elemento diferente se encuentra en la array restante. Entonces recorremos la array desde el cuarto elemento y simplemente verificamos si el valor del elemento actual es diferente al anterior o no.

A continuación se muestra la implementación de la idea anterior.
 

C++

// C++ program to find the only different
// element in an array.
#include <bits/stdc++.h>
using namespace std;
 
// Function to find minimum range
// increments to sort an array
int findTheOnlyDifferent(int arr[], int n)
{
    // Array size must be at least two.
    if (n == 1)
        return -1;
 
    // If there are two elements, then we
    // can return any one element as different
    if (n == 2)
        return 0;
 
    // Check if the different element is among
    // first three
    if (arr[0] == arr[1] && arr[0] != arr[2])
        return 2;
    if (arr[0] == arr[2] && arr[0] != arr[1])
        return 1;
    if (arr[1] == arr[2] && arr[0] != arr[1])
        return 0;
 
    // If we reach here, then first three elements
    // must be same (assuming that only one element
    // is different.
    for (int i = 3; i < n; i++)
        if (arr[i] != arr[i - 1])
            return i;
 
    return -1;
}
 
// Driver Code
int main()
{
    int arr[] = { 10, 20, 20, 20, 20 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << findTheOnlyDifferent(arr, n);
    return 0;
}

Java

// Java program to find the only different
// element in an array.
 
public class GFG
{
// Function to find minimum range
// increments to sort an array
static int findTheOnlyDifferent(int[] arr, int n)
{
    // Array size must be at least two.
    if (n == 1)
        return -1;
 
    // If there are two elements, then we
    // can return any one element as different
    if (n == 2)
        return 0;
 
    // Check if the different element is among
    // first three
    if (arr[0] == arr[1] && arr[0] != arr[2])
        return 2;
    if (arr[0] == arr[2] && arr[0] != arr[1])
        return 1;
    if (arr[1] == arr[2] && arr[0] != arr[1])
        return 0;
 
    // If we reach here, then first three elements
    // must be same (assuming that only one element
    // is different.
    for (int i = 3; i < n; i++)
        if (arr[i] != arr[i - 1])
            return i;
 
    return -1;
}
 
// Driver Code
public static void main(String args[])
{
    int[] arr = { 10, 20, 20, 20, 20 };
    int n = arr.length;
    System.out.println(findTheOnlyDifferent(arr, n));
}
 
// This code is contributed
// by Ryuga
 
}

Python3

# Python3 program to find the only
# different element in an array.
 
# Function to find minimum range
# increments to sort an array
def findTheOnlyDifferent(arr, n):
 
    # Array size must be at least two.
    if n == 1:
        return -1
 
    # If there are two elements,
    # then we can return any one
    # element as different
    if n == 2:
        return 0
 
    # Check if the different element
    # is among first three
    if arr[0] == arr[1] and arr[0] != arr[2]:
        return 2
    if arr[0] == arr[2] and arr[0] != arr[1]:
        return 1
    if arr[1] == arr[2] and arr[0] != arr[1]:
        return 0
 
    # If we reach here, then first
    # three elements must be same
    # (assuming that only one element
    # is different.
    for i in range(3, n):
        if arr[i] != arr[i - 1]:
            return i
 
    return -1
 
# Driver Code
if __name__ == "__main__":
     
    arr = [10, 20, 20, 20, 20]
    n = len(arr)
    print(findTheOnlyDifferent(arr, n))
 
# This code is contributed
# by Rituraj Jain

C#

// C# program to find the only different
// element in an array.
using System;
 
class GFG
{
// Function to find minimum range
// increments to sort an array
static int findTheOnlyDifferent(int[] arr, int n)
{
    // Array size must be at least two.
    if (n == 1)
        return -1;
 
    // If there are two elements, then we
    // can return any one element as different
    if (n == 2)
        return 0;
 
    // Check if the different element is among
    // first three
    if (arr[0] == arr[1] && arr[0] != arr[2])
        return 2;
    if (arr[0] == arr[2] && arr[0] != arr[1])
        return 1;
    if (arr[1] == arr[2] && arr[0] != arr[1])
        return 0;
 
    // If we reach here, then first three elements
    // must be same (assuming that only one element
    // is different.
    for (int i = 3; i < n; i++)
        if (arr[i] != arr[i - 1])
            return i;
 
    return -1;
}
 
// Driver Code
public static void Main()
{
    int[] arr = { 10, 20, 20, 20, 20 };
    int n = arr.Length;
    Console.Write(findTheOnlyDifferent(arr, n));
}
}
 
// This code is contributed
// by Akanksha Rai

PHP

<?php
// PHP program to find the only different
// element in an array.
 
// Function to find minimum range
// increments to sort an array
function findTheOnlyDifferent($arr, $n)
{
    // Array size must be at least two.
    if ($n == 1)
        return -1;
 
    // If there are two elements, then we
    // can return any one element as different
    if ($n == 2)
        return 0;
 
    // Check if the different element is among
    // first three
    if ($arr[0] == $arr[1] && $arr[0] != $arr[2])
        return 2;
    if ($arr[0] == $arr[2] && $arr[0] != $arr[1])
        return 1;
    if ($arr[1] == $arr[2] && $arr[0] != $arr[1])
        return 0;
 
    // If we reach here, then first three
    // elements must be same (assuming that
    // only one element is different.
    for ($i = 3; $i < $n; $i++)
        if ($arr[$i] != $arr[$i - 1])
            return $i;
 
    return -1;
}
 
// Driver Code
$arr = array(10, 20, 20, 20, 20);
$n = sizeof($arr);
echo findTheOnlyDifferent($arr, $n);
 
// This code is contributed by ajit
?>
Producción

0

Complejidad temporal: O(n) 
Espacio auxiliar: O(1)

SEGUNDO ENFOQUE: Uso de STL

Otro enfoque para este problema es mediante el uso del método vectorial. Simplemente copiaremos todos los elementos en otra array y luego simplemente compararemos el primer elemento de la nueva array ordenada con la anterior y el índice que no es el mismo será nuestra respuesta.

A continuación se muestra la implementación del enfoque anterior:

C++

#include <bits/stdc++.h>
using namespace std;
 
void solve()
{
  int arr[] = { 10, 20, 20, 20, 20 };
  int n = sizeof(arr) / sizeof(arr[0]);
  int arr2[n];
  for(int i=0;i<n;i++)
  {
    arr2[i]=arr[i];
  }
  sort(arr2,arr2+n);
  for (int i = 0; i < n; i++) {
        if (arr[i] != arr2[1]) {
            cout << i << "\n";
        }
    }
   
}
 
int main() {
 
    solve();
    return 0;
}
Producción

0

Complejidad de tiempo: O(n)

Espacio Auxiliar: O(1)
 

Publicación traducida automáticamente

Artículo escrito por kartik y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *