CareerCup

We can store the array in a HashSet and then covert back the HashSet in array. This will remove the duplicate elements. please Correct me if I am wrong.

1. Sort the input array.
2. Traverse the sorted array and fill the result array without duplicates.

void GetSortedArray(int* pArr, int n, int* & pResultArr, int& nrElems)
{
if (pArr == Null || n <= 0)
return NULL;

qSort(pArr, n);

vector<int> result;
for (int i = 0; i < n -1; i++)
{
if (pArr[i] != pArr[i+1])
result.push_back(pArr[i]);
}
result.push_back(pArr[i]);
nrElems = result.Count();
pResultArr = new int[nrElems];
Copy(result, pResultArr);
}

I think sorting is a little overkill, because we do not need these elements to be sorted at all. Couple of possible options:
1. Hash table
1. Using the idea from Set. Insert these elements into binary search tree. During insertion, all the duplicated elements will be filtered out.

def solve(input):
  dict = {}
  i = 0
  res = [] 
  while i < len(input):
    if input[i] not in dict:
      res.append(input[i])
      dict[input[i]]=''    
    i += 1
    pass
  return res 

if __name__ == '__main__':
  input = [1, 2, 2, 3, 3, 4]
  print "Input : ", input
  print "result : ", solve(input)
  pass

import java.util.*;
class duplicate
{
public int[] removeDuplicate(int []ar)
{
HashSet hs=new HashSet();//it will not allow duplicates to enter
int i,j=0;
int []newArray=new int[ar.length];//initialize new array of same length of given array
for(i=0;i<ar.length;i++)
{
hs.add(ar[i]);
}
Iterator ir=hs.iterator();
while(ir.hasNext())
{
newArray[j]=Integer.parseInt(ir.next().toString());
j++;
}
return newArray;
}
public static void main(String args[])
{
duplicate d=new duplicate();
int []a={20,10,12,10,15,10};
int []b=d.removeDuplicate(a);
for(int i=0;i<b.length;i++)
{
System.out.println(b[i]);
}
}
}

Use Hashtable :)

public static void RemoveDupes(int[] a)
        {
            
            Hashtable ht = new Hashtable();
            for (int i = 0; i < a.Length; i++)
            {
                if(!ht.ContainsKey(a[i]))
                ht.Add(a[i], i);
                
            }
            foreach (DictionaryEntry item in ht)
            {
                Console.WriteLine(item.Key);
            }
            Console.ReadLine();
        }

}

Try this in java:

int [] array=new int []{1,14,9,2,7,15,6,3,4,11,8,5,14,7,6,7,8,3,9,2,13,11,12};

List<Integer> myList = new ArrayList<Integer> ();

for (int i=0; i<array.length; i++)
{
if (!myList.contains(array[i]))
myList.add(array[i]);
}

Collections.sort(myList);

def unique():
   return list(set([int(i) for i in raw_input().split()]))

Simplest solution would be to maintain a counter for every number as you proceed through an array. For eg= Array A = [1,2,3,3,3,4,5] , Counter[1] = 1, counter[2] = 1 counter [3] =1, then when a pointer comes to 3 again, it will not add that element into a result array as counter[3] is already one. This will take O(n) time. The solution is best suited when space constraints are not given.

Make a new empty array, loop the input array for each element. Take the first element and save to the new array; take the second one and compare if it's same as all elements in the new array before you save it onto. Continue this process until reaches the end of the input array.

#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <map>
#include <string.h>
//method one:use map, since no hashmap, we can use stl c++ map implemented by rb tree.
typedef std::map<int,bool> Map;
int removeDup(int * a, int length){
if (!a ||length <=1) return length;
std::cout<<"Not null"<<std::endl;
Map m;
Map::iterator it;
int index = 0;
for (int i = 0;i<length;i++){
it = m.find(a[i]);
if (it == m.end()){
m[a[i]]=true;
//std::cout<<"Not dup "<<
if (index != i){
a[index] = a[i];
}
index++;
}
}
std::cout<<index<<std::endl;
return index;
}

Note:c++ has no hashmap, so here I use the stl map which is implemented by RB tree. If the number of elements are not quite large, look up and insertion can be considered as constant. However, one can implement his own hashmap to do this. The time complexity is O(n).

use a modified merge sort.
modification: when merge, if the values are equal don't merge one of them.

time complexity: O(nlogn)
space complexity: O(n)

Or you can modify a heap sort algorithm which has space complexity of O(1).

// Build Binary Search tree by reading each element and add only unique element- 
// now readback each element in inorder traversal to return back 
// O(nlogn) Time and O(n + n) space complexity
// wrote on notedpad hence no compile error checking performed...

public int[] GetUniqeRecord(int[] arr)
{
	if(arr == null) return null;
	if(arr.Length == 1) return arr;

	// Build Binary search tree
	int count;
	Node root = CreateBinaryTree(arr,out count);
	
	return uniqueRecord(root);
	
	// Readh binary search tree

}

public class Node
{
	public int data{get;set;}
	public Node left{get;set;}
	public Node right{get;set;}
	public Node(int data)
	{
		this.data = data;
	}
}

publc int[] uniqueRecord(Node root,int count)
{
	Stack s = new Stack();
	int[] arr = new int[count];
	Node n = root;
	s.Push(n);
	int i=0;
	while(!s.IsEmpty() || n!= null)
	{
		if(n != null)
		{			
			s.push(n);
			arr[i++] = n.data;
			n = n.left;			
		}
		else
		{
			n= s.Pop();
			n = n.right;	
		}
	}

	return arr;
}

public Node CreateBinaryTree(int[] arr,ref int cout)
{

	Node root = null;
	 
	root = new Node(arr[0]);
	Node temp = null;
	node pre;
	bool duplicate = false;
	for(int i=1;i<arr.Legth-1;i++)
	{

		temp = root;
		duplicate = false;	
		while(temp != null)
		{	
			pre = temp;
			if(arr[i] > temp.data)
			{
				temp = temp.right;
			}
			else if(arr[i] < temp.data)
			{
				temp = temp.left;
			}
			else
			{
				duplicate = true;
				break;	
			}			
		}		
		

		if(!duplicatae)
		{
			if(arr[i] > pre.data)
				pre.right = new Node(arr[i]);
			else
				pre.left = new Node(arr[i]);
			count++;
		}
	}
}

The one way is to maintain a dictionary. HashMap<Char,boolean>

used HashSet and an additional array, the space complexity is not O(n). Not efficient solution. Please suggest how can I improve it.

public class Unique {
    public static void main(String[] args){

        int[] dup={1,2,4,3,2,2,1,3,4,5,7,6,8,9,8,8,7};

        Set set=new HashSet();

        for(int i=0;i<dup.length;i++){

            if(!set.contains(dup[i])) {

                set.add(dup[i]);

            }

        }

        int size=set.size() ;
        int[] unique=new int[size];

        int k=0;
        for(int i=0;i<dup.length;i++){

            if(set.contains(dup[i])){

                unique[k++]=dup[i];
                set.remove(dup[i]);    //removing from the set as soon as it is added to the array

            }

        }
        for(int i=0;i<size;i++){
            System.out.print(unique[i]);
        }

    }
}