Find the first element occurs twice in a number array

The most effective solution is to use hash to keep track of the element counts, while using DLL list to keep track of the potential candidates seen so far, meanwhile the value of the hash table is a pointer to each node in the DLL, so we can quickly remove one node from the DLL.

Data structure: aggregated data structure using hash table O(1) lookup and DLL O(1) deletion and access to the head.

/*

* http://www.geeksforgeeks.org/microsoft-interview-set-37-sde-1/

* Given numbers a1…an find the minimum index, whose element occurs 

* twice in the array. Do it in one pass of the array ( or less that O(n) if possible?)

*/

public static int findFirstNoRepeatNumber(int[] numbers){

Map<Integer, Node> store = new HashMap<Integer, Node>();

Node head = null;

Node tail = null;

for(int i : numbers){

if(store.containsKey(i)){

Node found = store.get(i);

found.times = found.times + 1;

if(found.times==2){

//add it to DLL when repeat twice

if(head==null){

head = found;

tail = found;

}else{

found.pre = tail;

tail.next = found;

tail = found;

}

}

if(found.times>2){

//remove found from DLL

if(!(found.pre==null && found.next==null)){

if(found.pre==null){

head = found.next;

}else if(found.next ==null){

tail = found.pre;

}else{

found.pre.next = found.next;

found.next.pre = found.pre;

}

found.pre = null;

found.next = null;

}

}

}else{

//create node and add to map for first time

Node newNode = new Node();

newNode.index = i;

newNode.times = 1;

store.put(i, newNode);

}

}

return head.index;

}