Imprimir todos os elementos distintos de uma determinada array de inteiros
Dado um array inteiro, imprime todos os elementos distintos no array. O array fornecido pode conter duplicatas e a saída deve imprimir cada elemento apenas uma vez. A array fornecida não está classificada.
Exemplos:
Input: arr[] = {12, 10, 9, 45, 2, 10, 10, 45}
Output: 12, 10, 9, 45, 2
Input: arr[] = {1, 2, 3, 4, 5}
Output: 1, 2, 3, 4, 5
Input: arr[] = {1, 1, 1, 1, 1}
Output: 1
Uma solução simples é usar loops aninhados twp. O loop externo escolhe um elemento um por um, começando do elemento mais à esquerda. O loop interno verifica se o elemento está presente no lado esquerdo dele. Se estiver presente, então ignora o elemento, senão imprime o elemento. A seguir está a implementação do algoritmo simples.
// C++ program to print all distinct elements in a given array
#include <bits/stdc++.h>
using namespace std;
void printDistinct(int arr[], int n)
{
// Pick all elements one by one
for (int i=0; i<n; i++)
{
// Check if the picked element is already printed
int j;
for (j=0; j<i; j++)
if (arr[i] == arr[j])
break;
// If not printed earlier, then print it
if (i == j)
cout << arr[i] << " ";
}
}
// Driver program to test above function
int main()
{
int arr[] = {6, 10, 5, 4, 9, 120, 4, 6, 10};
int n = sizeof(arr)/sizeof(arr[0]);
printDistinct(arr, n);
return 0;
}// Java program to print all distinct
// elements in a given array
import java.io.*;
class GFG {
static void printDistinct(int arr[], int n)
{
// Pick all elements one by one
for (int i = 0; i < n; i++)
{
// Check if the picked element
// is already printed
int j;
for (j = 0; j < i; j++)
if (arr[i] == arr[j])
break;
// If not printed earlier,
// then print it
if (i == j)
System.out.print( arr[i] + " ");
}
}
// Driver program
public static void main (String[] args)
{
int arr[] = {6, 10, 5, 4, 9, 120, 4, 6, 10};
int n = arr.length;
printDistinct(arr, n);
}
}
// This code is contributed by vt_m# python program to print all distinct
# elements in a given array
def printDistinct(arr, n):
# Pick all elements one by one
for i in range(0, n):
# Check if the picked element
# is already printed
d = 0
for j in range(0, i):
if (arr[i] == arr[j]):
d = 1
break
# If not printed earlier,
# then print it
if (d == 0):
print(arr[i])
# Driver program to test above function
arr = [6, 10, 5, 4, 9, 120, 4, 6, 10]
n = len(arr)
printDistinct(arr, n)
# This code is contributed by Sam007.// C# program to print all distinct
// elements in a given array
using System;
class GFG {
static void printDistinct(int []arr, int n)
{
// Pick all elements one by one
for (int i = 0; i < n; i++)
{
// Check if the picked element
// is already printed
int j;
for (j = 0; j < i; j++)
if (arr[i] == arr[j])
break;
// If not printed earlier,
// then print it
if (i == j)
Console.Write(arr[i] + " ");
}
}
// Driver program
public static void Main ()
{
int []arr = {6, 10, 5, 4, 9, 120,
4, 6, 10};
int n = arr.Length;
printDistinct(arr, n);
}
}
// This code is contributed by Sam007.<?php
// PHP program to print all distinct
// elements in a given array
function printDistinct($arr, $n)
{
// Pick all elements one by one
for($i = 0; $i < $n; $i++)
{
// Check if the picked element
// is already printed
$j;
for($j = 0; $j < $i; $j++)
if ($arr[$i] == $arr[$j])
break;
// If not printed
// earlier, then print it
if ($i == $j)
echo $arr[$i] , " ";
}
}
// Driver Code
$arr = array(6, 10, 5, 4, 9, 120, 4, 6, 10);
$n = sizeof($arr);
printDistinct($arr, $n);
// This code is contributed by nitin mittal
?><script>
//Program to print all distinct elements in a given array
function printDistinct(arr, n)
{
// Pick all elements one by one
for (let i=0; i<n; i++)
{
// Check if the picked element is already printed
var j;
for (j=0; j<i; j++)
if (arr[i] == arr[j])
break;
// If not printed earlier, then print it
if (i == j)
document.write(arr[i] + " ");
}
}
// Driver program to test above function
arr = new Array(6, 10, 5, 4, 9, 120, 4, 6, 10);
n = arr.length;
printDistinct(arr, n);
//This code is contributed by simranarora5sos
</script>Saída:
6 10 5 4 9 120
A complexidade de tempo da solução acima é O (n 2 ). Podemos usar a classificação para resolver o problema em tempo O (nLogn). A ideia é simples, primeiro ordene o array de forma que todas as ocorrências de cada elemento se tornem consecutivas. Uma vez que as ocorrências se tornam consecutivas, podemos percorrer o array ordenado e imprimir elementos distintos em tempo O (n). A seguir está a implementação da ideia.
// C++ program to print all distinct elements in a given array
#include <bits/stdc++.h>
using namespace std;
void printDistinct(int arr[], int n)
{
// First sort the array so that all occurrences become consecutive
sort(arr, arr + n);
// Traverse the sorted array
for (int i=0; i<n; i++)
{
// Move the index ahead while there are duplicates
while (i < n-1 && arr[i] == arr[i+1])
i++;
// print last occurrence of the current element
cout << arr[i] << " ";
}
}
// Driver program to test above function
int main()
{
int arr[] = {6, 10, 5, 4, 9, 120, 4, 6, 10};
int n = sizeof(arr)/sizeof(arr[0]);
printDistinct(arr, n);
return 0;
}// Java program to print all distinct
// elements in a given array
import java.io.*;
import java .util.*;
class GFG
{
static void printDistinct(int arr[], int n)
{
// First sort the array so that
// all occurrences become consecutive
Arrays.sort(arr);
// Traverse the sorted array
for (int i = 0; i < n; i++)
{
// Move the index ahead while
// there are duplicates
while (i < n - 1 && arr[i] == arr[i + 1])
i++;
// print last occurrence of
// the current element
System.out.print(arr[i] +" ");
}
}
// Driver program
public static void main (String[] args)
{
int arr[] = {6, 10, 5, 4, 9, 120, 4, 6, 10};
int n = arr.length;
printDistinct(arr, n);
}
}
// This code is contributed by vt_m# Python program to print all distinct
# elements in a given array
def printDistinct(arr, n):
# First sort the array so that
# all occurrences become consecutive
arr.sort();
# Traverse the sorted array
for i in range(n):
# Move the index ahead while there are duplicates
if(i < n-1 and arr[i] == arr[i+1]):
while (i < n-1 and (arr[i] == arr[i+1])):
i+=1;
# print last occurrence of the current element
else:
print(arr[i], end=" ");
# Driver code
arr = [6, 10, 5, 4, 9, 120, 4, 6, 10];
n = len(arr);
printDistinct(arr, n);
# This code has been contributed by 29AjayKumar// C# program to print all distinct
// elements in a given array
using System;
class GFG {
static void printDistinct(int []arr, int n)
{
// First sort the array so that
// all occurrences become consecutive
Array.Sort(arr);
// Traverse the sorted array
for (int i = 0; i < n; i++)
{
// Move the index ahead while
// there are duplicates
while (i < n - 1 && arr[i] == arr[i + 1])
i++;
// print last occurrence of
// the current element
Console.Write(arr[i] + " ");
}
}
// Driver program
public static void Main ()
{
int []arr = {6, 10, 5, 4, 9, 120, 4, 6, 10};
int n = arr.Length;
printDistinct(arr, n);
}
}
// This code is contributed by Sam007.<?php
// PHP program to print all distinct
// elements in a given array
function printDistinct( $arr, $n)
{
// First sort the array so
// that all occurrences
// become consecutive
sort($arr);
// Traverse the sorted array
for ($i = 0; $i < $n; $i++)
{
// Move the index ahead
// while there are duplicates
while ($i < $n - 1 and
$arr[$i] == $arr[$i + 1])
$i++;
// print last occurrence
// of the current element
echo $arr[$i] , " ";
}
}
// Driver Code
$arr = array(6, 10, 5, 4, 9, 120, 4, 6, 10);
$n = count($arr);
printDistinct($arr, $n);
// This code is contributed by anuj_67.
?><script>
// JavaScript program to print all
// distinct elements in a given array
function printDistinct(arr, n)
{
// First sort the array so that all
// occurrences become consecutive
arr.sort((a, b) => a - b);
// Traverse the sorted array
for (let i=0; i<n; i++)
{
// Move the index ahead while
// there are duplicates
while (i < n-1 && arr[i] == arr[i+1])
i++;
// print last occurrence of the
// current element
document.write(arr[i] + " ");
}
}
// Driver program to test above function
let arr = [6, 10, 5, 4, 9, 120, 4, 6, 10];
let n = arr.length;
printDistinct(arr, n);
// This code is contributed by Surbhi Tyagi.
</script>Saída:
4 5 6 9 10 120
Podemos usar Hashing para resolver isso em tempo O (n) em média. A ideia é percorrer o array fornecido da esquerda para a direita e controlar os elementos visitados em uma tabela hash. A seguir está a implementação da ideia.
/* CPP program to print all distinct elements
of a given array */
#include<bits/stdc++.h>
using namespace std;
// This function prints all distinct elements
void printDistinct(int arr[],int n)
{
// Creates an empty hashset
unordered_set<int> s;
// Traverse the input array
for (int i=0; i<n; i++)
{
// If not present, then put it in
// hashtable and print it
if (s.find(arr[i])==s.end())
{
s.insert(arr[i]);
cout << arr[i] << " ";
}
}
}
// Driver method to test above method
int main ()
{
int arr[] = {10, 5, 3, 4, 3, 5, 6};
int n=7;
printDistinct(arr,n);
return 0;
}/* Java program to print all distinct elements of a given array */
import java.util.*;
class Main
{
// This function prints all distinct elements
static void printDistinct(int arr[])
{
// Creates an empty hashset
HashSet<Integer> set = new HashSet<>();
// Traverse the input array
for (int i=0; i<arr.length; i++)
{
// If not present, then put it in hashtable and print it
if (!set.contains(arr[i]))
{
set.add(arr[i]);
System.out.print(arr[i] + " ");
}
}
}
// Driver method to test above method
public static void main (String[] args)
{
int arr[] = {10, 5, 3, 4, 3, 5, 6};
printDistinct(arr);
}
}# Python3 program to print all distinct elements
# of a given array
# This function prints all distinct elements
def printDistinct(arr, n):
# Creates an empty hashset
s = dict();
# Traverse the input array
for i in range(n):
# If not present, then put it in
# hashtable and print it
if (arr[i] not in s.keys()):
s[arr[i]] = arr[i];
print(arr[i], end = " ");
# Driver Code
arr = [10, 5, 3, 4, 3, 5, 6];
n = 7;
printDistinct(arr, n);
# This code is contributed by Princi Singh// C# program to print all distinct
// elements of a given array
using System;
using System.Collections.Generic;
class GFG
{
// This function prints all
// distinct elements
public static void printDistinct(int[] arr)
{
// Creates an empty hashset
HashSet<int> set = new HashSet<int>();
// Traverse the input array
for (int i = 0; i < arr.Length; i++)
{
// If not present, then put it
// in hashtable and print it
if (!set.Contains(arr[i]))
{
set.Add(arr[i]);
Console.Write(arr[i] + " ");
}
}
}
// Driver Code
public static void Main(string[] args)
{
int[] arr = new int[] {10, 5, 3, 4, 3, 5, 6};
printDistinct(arr);
}
}
// This code is contributed by Shrikant13<script>
// Javascript program to print all distinct elements of a given array
// This function prints all distinct elements
function printDistinct(arr)
{
// Creates an empty hashset
let set = new Set();
// Traverse the input array
for (let i=0; i<arr.length; i++)
{
// If not present, then put it in hashtable and print it
if (!set.has(arr[i]))
{
set.add(arr[i]);
document.write(arr[i] + " ");
}
}
}
// Driver program
let arr = [10, 5, 3, 4, 3, 5, 6];
printDistinct(arr);
</script>Saída:
10 5 3 4 6
Mais uma vantagem do hash sobre a classificação é que os elementos são impressos na mesma ordem em que estão na array de entrada.
Outra abordagem:
1. Coloque todos os inteiros de entrada na chave do hashmap
2. Imprima o conjunto de chaves fora do loop
import java.util.HashMap;
public class UniqueInArray2 {
public static void main(String args[])
{
int ar[] = { 10, 5, 3, 4, 3, 5, 6 };
HashMap<Integer,Integer> hm = new HashMap<Integer,Integer>();
for (int i = 0; i < ar.length; i++) {
hm.put(ar[i], i);
}
// Using hm.keySet() to print output
// reduces time complexity. - Lokesh
System.out.println(hm.keySet());
}
}// C# implementation of the approach
using System;
using System.Collections.Generic;
public class UniqueInArray2
{
public static void Main(String []args)
{
int []ar = { 10, 5, 3, 4, 3, 5, 6 };
Dictionary<int,int> hm = new Dictionary<int,int>();
for (int i = 0; i < ar.Length; i++)
{
if(hm.ContainsKey(ar[i]))
hm.Remove(ar[i]);
hm.Add(ar[i], i);
}
// Using hm.Keys to print output
// reduces time complexity. - Lokesh
var v = hm.Keys;
foreach(int a in v)
Console.Write(a+" ");
}
}
/* This code contributed by PrinciRaj1992 */<iframe allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen="" frameborder="0" height="374" src="https://www.youtube.com/embed/rd43j78S10A?list=PLqM7alHXFySEQDk2MDfbwEdjd2svVJH9p" width="665"></iframe>
Escreva comentários se encontrar algo incorreto ou se quiser compartilhar mais informações sobre o tópico discutido acima.
As postagens do blog Acervo Lima te ajudaram? Nos ajude a manter o blog no ar!
Faça uma doação para manter o blog funcionando.
70% das doações são no valor de R$ 5,00...
Diógenes Lima da Silva
