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;
}