Blue Ocean: 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.
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;
}
Read full article from Blue Ocean: Find the first element occurs twice in a number array