Dada una array arr que tiene números que aparecen dos o una vez. La tarea es identificar los números que ocurren solo una vez en la array.
Nota: Los duplicados aparecen uno al lado del otro cada vez. Puede haber algunos números que pueden ocurrir a la vez y simplemente suponga que se trata de una array giratoria a la derecha (solo diga que una array puede rotar k veces hacia la derecha). El orden de los elementos en la salida no importa.
Ejemplos:
Input: arr[] = { 7, 7, 8, 8, 9, 1, 1, 4, 2, 2 }
Output: 9 4
Input: arr[] = {-9, -8, 4, 4, 5, 5, -1}
Output: -9 -8 -1
Método 1: Uso de la clasificación .
- Ordenar la array.
- Compruebe cada elemento en el índice i (excepto el primer y último elemento), si
arr[i] != arr[i-1] && arr [i] != arr[i+1]
- Para el primer elemento, compruebe si arr[0] != arr[1] .
- Para el último elemento, compruebe si arr[n-1] != arr[n-2] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the elements that
// appeared only once in the array
void occurredOnce(int arr[], int n)
{
// Sort the array
sort(arr, arr + n);
// Check for first element
if (arr[0] != arr[1])
cout << arr[0] << " ";
// Check for all the elements if it is different
// its adjacent elements
for (int i = 1; i < n - 1; i++)
if (arr[i] != arr[i + 1] && arr[i] != arr[i - 1])
cout << arr[i] << " ";
// Check for the last element
if (arr[n - 2] != arr[n - 1])
cout << arr[n - 1] << " ";
}
// Driver code
int main()
{
int arr[] = { 7, 7, 8, 8, 9, 1, 1, 4, 2, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
occurredOnce(arr, n);
return 0;
}
Java
// Java implementation
// of above approach
import java.util.*;
class GFG
{
// Function to find the elements that
// appeared only once in the array
static void occurredOnce(int arr[], int n)
{
// Sort the array
Arrays.sort(arr);
// Check for first element
if (arr[0] != arr[1])
System.out.println(arr[0] + " ");
// Check for all the elements
// if it is different
// its adjacent elements
for (int i = 1; i < n - 1; i++)
if (arr[i] != arr[i + 1] &&
arr[i] != arr[i - 1])
System.out.print(arr[i] + " ");
// Check for the last element
if (arr[n - 2] != arr[n - 1])
System.out.print(arr[n - 1] + " ");
}
// Driver code
public static void main(String args[])
{
int arr[] = {7, 7, 8, 8, 9,
1, 1, 4, 2, 2};
int n = arr.length;
occurredOnce(arr, n);
}
}
// This code is contributed
// by Arnab Kundu
Python3
# Python 3 implementation # of above approach # Function to find the elements # that appeared only once in # the array def occurredOnce(arr, n): # Sort the array arr.sort() # Check for first element if arr[0] != arr[1]: print(arr[0], end = " ") # Check for all the elements # if it is different its # adjacent elements for i in range(1, n - 1): if (arr[i] != arr[i + 1] and arr[i] != arr[i - 1]): print( arr[i], end = " ") # Check for the last element if arr[n - 2] != arr[n - 1]: print(arr[n - 1], end = " ") # Driver code if __name__ == "__main__": arr = [ 7, 7, 8, 8, 9, 1, 1, 4, 2, 2 ] n = len(arr) occurredOnce(arr, n) # This code is contributed # by ChitraNayal
C#
// C# implementation
// of above approach
using System;
class GFG
{
// Function to find the elements that
// appeared only once in the array
static void occurredOnce(int[] arr, int n)
{
// Sort the array
Array.Sort(arr);
// Check for first element
if (arr[0] != arr[1])
Console.Write(arr[0] + " ");
// Check for all the elements
// if it is different
// its adjacent elements
for (int i = 1; i < n - 1; i++)
if (arr[i] != arr[i + 1] &&
arr[i] != arr[i - 1])
Console.Write(arr[i] + " ");
// Check for the last element
if (arr[n - 2] != arr[n - 1])
Console.Write(arr[n - 1] + " ");
}
// Driver code
public static void Main()
{
int[] arr = {7, 7, 8, 8, 9,
1, 1, 4, 2, 2};
int n = arr.Length;
occurredOnce(arr, n);
}
}
// This code is contributed
// by ChitraNayal
PHP
<?php
// PHP implementation
// of above approach
// Function to find the elements
// that appeared only once in
// the array
function occurredOnce(&$arr, $n)
{
// Sort the array
sort($arr);
// Check for first element
if ($arr[0] != $arr[1])
echo $arr[0]." ";
// Check for all the elements
// if it is different its
// adjacent elements
for ($i = 1; $i < $n - 1; $i++)
if ($arr[$i] != $arr[$i + 1] &&
$arr[$i] != $arr[$i - 1])
echo $arr[$i]." ";
// Check for the last element
if ($arr[$n - 2] != $arr[$n - 1])
echo $arr[$n - 1]." ";
}
// Driver code
$arr = array(7, 7, 8, 8, 9,
1, 1, 4, 2, 2);
$n = sizeof($arr);
occurredOnce($arr, $n);
// This code is contributed
// by ChitraNayal
?>
Javascript
<script>
// Javascript implementation
// of above approach
// Function to find the elements that
// appeared only once in the array
function occurredOnce(arr,n)
{
// Sort the array
arr.sort(function(a,b){return a-b;});
// Check for first element
if (arr[0] != arr[1])
document.write(arr[0] + " ");
// Check for all the elements
// if it is different
// its adjacent elements
for (let i = 1; i < n - 1; i++)
if (arr[i] != arr[i + 1] &&
arr[i] != arr[i - 1])
document.write(arr[i] + " ");
// Check for the last element
if (arr[n - 2] != arr[n - 1])
document.write(arr[n - 1] + " ");
}
// Driver code
let arr=[7, 7, 8, 8, 9,
1, 1, 4, 2, 2];
let n = arr.length;
occurredOnce(arr, n);
// This code is contributed by rag2127
</script>
Producción
4 9
Complejidad de tiempo: O(Nlogn)
Complejidad de espacio: O(1)
Método 2: (usando hash ) : en C++, unordered_map se puede usar para hash.
- Atraviesa la array.
- Almacene cada elemento con su aparición en unordered_map.
- Atraviese unordered_map e imprima todos los elementos con la ocurrencia 1.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find elements
// that appeared only once
#include <bits/stdc++.h>
using namespace std;
// Function to find the elements that
// appeared only once in the array
void occurredOnce(int arr[], int n)
{
unordered_map<int, int> mp;
// Store all the elements in the map with
// their occurrence
for (int i = 0; i < n; i++)
mp[arr[i]]++;
// Traverse the map and print all the
// elements with occurrence 1
for (auto it = mp.begin(); it != mp.end(); it++)
if (it->second == 1)
cout << it->first << " ";
}
// Driver code
int main()
{
int arr[] = { 7, 7, 8, 8, 9, 1, 1, 4, 2, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
occurredOnce(arr, n);
return 0;
}
Java
// Java implementation to find elements
// that appeared only once
import java.util.*;
import java.io.*;
class GFG
{
// Function to find the elements that
// appeared only once in the array
static void occurredOnce(int[] arr, int n)
{
HashMap<Integer, Integer> mp = new HashMap<>();
// Store all the elements in the map with
// their occurrence
for (int i = 0; i < n; i++)
{
if (mp.containsKey(arr[i]))
mp.put(arr[i], 1 + mp.get(arr[i]));
else
mp.put(arr[i], 1);
}
// Traverse the map and print all the
// elements with occurrence 1
for (Map.Entry entry : mp.entrySet())
{
if (Integer.parseInt(String.valueOf(entry.getValue())) == 1)
System.out.print(entry.getKey() + " ");
}
}
// Driver code
public static void main(String args[])
{
int[] arr = { 7, 7, 8, 8, 9, 1, 1, 4, 2, 2 };
int n = arr.length;
occurredOnce(arr, n);
}
}
// This code is contributed by rachana soma
Python3
# Python3 implementation to find elements # that appeared only once import math as mt # Function to find the elements that # appeared only once in the array def occurredOnce(arr, n): mp = dict() # Store all the elements in the # map with their occurrence for i in range(n): if arr[i] in mp.keys(): mp[arr[i]] += 1 else: mp[arr[i]] = 1 # Traverse the map and print all # the elements with occurrence 1 for it in mp: if mp[it] == 1: print(it, end = " ") # Driver code arr = [7, 7, 8, 8, 9, 1, 1, 4, 2, 2] n = len(arr) occurredOnce(arr, n) # This code is contributed by # Mohit Kumar 29
C#
// C# implementation to find elements
// that appeared only once
using System;
using System.Collections.Generic;
class GFG
{
// Function to find the elements that
// appeared only once in the array
static void occurredOnce(int[] arr, int n)
{
Dictionary<int, int> mp = new Dictionary<int, int>();
// Store all the elements in the map with
// their occurrence
for (int i = 0; i < n; i++)
{
if (mp.ContainsKey(arr[i]))
mp[arr[i]] = 1 + mp[arr[i]];
else
mp.Add(arr[i], 1);
}
// Traverse the map and print all the
// elements with occurrence 1
foreach(KeyValuePair<int, int> entry in mp)
{
if (Int32.Parse(String.Join("", entry.Value)) == 1)
Console.Write(entry.Key + " ");
}
}
// Driver code
public static void Main(String []args)
{
int[] arr = { 7, 7, 8, 8, 9, 1, 1, 4, 2, 2 };
int n = arr.Length;
occurredOnce(arr, n);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript implementation to find elements
// that appeared only once
// Function to find the elements that
// appeared only once in the array
function occurredOnce(arr, n)
{
let mp = new Map();
// Store all the elements in the map
// with their occurrence
for(let i = 0; i < n; i++)
{
if (mp.has(arr[i]))
mp.set(arr[i], 1 + mp.get(arr[i]));
else
mp.set(arr[i], 1);
}
// Traverse the map and print all the
// elements with occurrence 1
for(let [key, value] of mp.entries())
{
if (value == 1)
document.write(key + " ");
}
}
// Driver code
let arr = [ 7, 7, 8, 8, 9,
1, 1, 4, 2, 2 ];
let n = arr.length;
occurredOnce(arr, n);
// This code is contributed by avanitrachhadiya2155
</script>
Producción
4 9
Complejidad temporal: O(N)
Complejidad espacial: O(N)
Método-3: Usando suposiciones dadas.
Se da que una array se puede rotar en cualquier momento y los duplicados aparecerán uno al lado del otro cada vez. Entonces, después de rotar, el primer y el último elemento aparecerán uno al lado del otro.
- Comprueba si el primer y el último elemento son iguales. Si es así, comience a atravesar los elementos entre ellos.
- Comprueba si el elemento actual es igual al elemento del índice inmediatamente anterior. En caso afirmativo, marque lo mismo para el siguiente elemento.
- Si no, imprime el elemento actual.
C++
// C++ implementation to find elements
// that appeared only once
#include <bits/stdc++.h>
using namespace std;
// Function to find the elements that
// appeared only once in the array
void occurredOnce(int arr[], int n)
{
int i = 1, len = n;
// Check if the first and last element is equal
// If yes, remove those elements
if (arr[0] == arr[len - 1]) {
i = 2;
len--;
}
// Start traversing the remaining elements
for (; i < n; i++)
// Check if current element is equal to
// the element at immediate previous index
// If yes, check the same for next element
if (arr[i] == arr[i - 1])
i++;
// Else print the current element
else
cout << arr[i - 1] << " ";
// Check for the last element
if (arr[n - 1] != arr[0] && arr[n - 1] != arr[n - 2])
cout << arr[n - 1];
}
// Driver code
int main()
{
int arr[] = { 7, 7, 8, 8, 9, 1, 1, 4, 2, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
occurredOnce(arr, n);
return 0;
}
Java
// Java implementation to find
// elements that appeared only once
class GFG
{
// Function to find the elements that
// appeared only once in the array
static void occurredOnce(int arr[], int n)
{
int i = 1, len = n;
// Check if the first and last
// element is equal. If yes,
// remove those elements
if (arr[0] == arr[len - 1])
{
i = 2;
len--;
}
// Start traversing the
// remaining elements
for (; i < n; i++)
// Check if current element is
// equal to the element at
// immediate previous index
// If yes, check the same
// for next element
if (arr[i] == arr[i - 1])
i++;
// Else print the current element
else
System.out.print(arr[i - 1] + " ");
// Check for the last element
if (arr[n - 1] != arr[0] &&
arr[n - 1] != arr[n - 2])
System.out.print(arr[n - 1]);
}
// Driver code
public static void main(String args[])
{
int arr[] = {7, 7, 8, 8, 9,
1, 1, 4, 2, 2};
int n = arr.length;
occurredOnce(arr, n);
}
}
// This code is contributed
// by Arnab Kundu
Python3
# Python 3 implementation to find # elements that appeared only once # Function to find the elements that # appeared only once in the array def occurredOnce(arr, n): i = 1 len = n # Check if the first and # last element is equal # If yes, remove those elements if arr[0] == arr[len - 1]: i = 2 len -= 1 # Start traversing the # remaining elements while i < n: # Check if current element is # equal to the element at # immediate previous index # If yes, check the same for # next element if arr[i] == arr[i - 1]: i += 1 # Else print the current element else: print(arr[i - 1], end = " ") i += 1 # Check for the last element if (arr[n - 1] != arr[0] and arr[n - 1] != arr[n - 2]): print(arr[n - 1]) # Driver code if __name__ == "__main__": arr = [ 7, 7, 8, 8, 9, 1, 1, 4, 2, 2 ] n = len(arr) occurredOnce(arr, n) # This code is contributed # by ChitraNayal
C#
// C# implementation to find
// elements that appeared only once
using System;
class GFG
{
// Function to find the elements that
// appeared only once in the array
static void occurredOnce(int[] arr, int n)
{
int i = 1, len = n;
// Check if the first and last
// element is equal. If yes,
// remove those elements
if (arr[0] == arr[len - 1])
{
i = 2;
len--;
}
// Start traversing the
// remaining elements
for (; i < n; i++)
// Check if current element is
// equal to the element at
// immediate previous index
// If yes, check the same
// for next element
if (arr[i] == arr[i - 1])
i++;
// Else print the current element
else
Console.Write(arr[i - 1] + " ");
// Check for the last element
if (arr[n - 1] != arr[0] &&
arr[n - 1] != arr[n - 2])
Console.Write(arr[n - 1]);
}
// Driver code
public static void Main()
{
int[] arr = {7, 7, 8, 8, 9,
1, 1, 4, 2, 2};
int n = arr.Length;
occurredOnce(arr, n);
}
}
// This code is contributed
// by ChitraNayal
PHP
<?php
// PHP implementation to find
// elements that appeared only once
// Function to find the elements that
// appeared only once in the array
function occurredOnce(&$arr, $n)
{
$i = 1;
$len = $n;
// Check if the first and last
// element is equal. If yes,
// remove those elements
if ($arr[0] == $arr[$len - 1])
{
$i = 2;
$len--;
}
// Start traversing the
// remaining elements
for (; $i < $n; $i++)
// Check if current element is
// equal to the element at
// immediate previous index
// If yes, check the same for
// next element
if ($arr[$i] == $arr[$i - 1])
$i++;
// Else print the current element
else
echo $arr[$i - 1] . " ";
// Check for the last element
if ($arr[$n - 1] != $arr[0] &&
$arr[$n - 1] != $arr[$n - 2])
echo $arr[$n - 1];
}
// Driver code
$arr = array(7, 7, 8, 8, 9,
1, 1, 4, 2, 2);
$n = sizeof($arr);
occurredOnce($arr, $n);
// This code is contributed
// by ChitraNayal
?>
Javascript
<script>
// Javascript implementation to find
// elements that appeared only once
// Function to find the elements that
// appeared only once in the array
function occurredOnce(arr, n)
{
var i = 1, len = n;
// Check if the first and last
// element is equal. If yes,
// remove those elements
if (arr[0] == arr[len - 1])
{
i = 2;
len--;
}
// Start traversing the
// remaining elements
for(; i < n; i++)
// Check if current element is
// equal to the element at
// immediate previous index
// If yes, check the same
// for next element
if (arr[i] == arr[i - 1])
i++;
// Else print the current element
else
document.write(arr[i - 1] + " ");
// Check for the last element
if (arr[n - 1] != arr[0] &&
arr[n - 1] != arr[n - 2])
document.write(arr[n - 1]);
}
// Driver code
var arr = [ 7, 7, 8, 8, 9,
1, 1, 4, 2, 2 ];
var n = arr.length;
occurredOnce(arr, n);
// This code is contributed by Ankita saini
</script>
Producción
9 4
Complejidad de tiempo: O(N)
Complejidad de espacio: O(1)
Método n.º 4: Uso de las funciones integradas de Python:
- Cuente las frecuencias de cada elemento usando la función Contador
- Recorra la array de frecuencias e imprima todos los elementos con ocurrencia 1.
A continuación se muestra la implementación.
Python3
# Python3 implementation to find elements # that appeared only once from collections import Counter # Function to find the elements that # appeared only once in the array def occurredOnce(arr, n): #counting frequency of every element using Counter mp=Counter(arr) # Traverse the map and print all # the elements with occurrence 1 for it in mp: if mp[it] == 1: print(it, end = " ") # Driver code arr = [7, 7, 8, 8, 9, 1, 1, 4, 2, 2] n = len(arr) occurredOnce(arr, n) # This code is contributed by vikkycirus
Producción
9 4
Complejidad de tiempo: O(n)
Publicación traducida automáticamente
Artículo escrito por namankedia y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA