Question

design an efficient algorithm that, on input a set of n real numbers {x1, . . . , xn}, outputs all distinct numbers in the set. For example, if your input is {5, 10, 9, 10, 8, 5, 12, 11, 12, 9, 7, 6, 8, 5}, then you should output {5, 10, 9, 8, 11, 12, 7, 6} (any ordering of these number is acceptable).

Answer 1

/*

We can Use Hashing to solve this in O(n) time on average. The idea is to traverse the given array from left to right and keep track of visited elements in a hash table. Following is the implementation of the idea.

*/

/* 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[] = {5, 10, 9, 10, 8, 5, 12, 11, 12, 9, 7, 6, 8, 5};
printDistinct(arr);
}
}