Ajeet
BAN USERLearn & Share
Note: If the value type is integer than we can use following algorithm to remove all duplicates in O(n) complexity.
Algorithm:
============
Node pre = null;
removeDuplicates(LinkedList list){
Node tmp = start;
integer bitarray = 0;
while(tmp ! = null){
integer x = 1; // 0000 0001
integer value = temp.value;
/***********
Left shift inter x (1) by number of places equals to value
If value =4, After below operation x will become 0000 1000
***********/
x = x << num;
/*****************************
Bitwise and operation to add above result in a bitarray.
********************************/
if((bitarray & x) != 0){
System.out.println("Duplicate found in given linked list: " + num);
/**************************
It will delete current node with O(1) time complexity and will return next node;
We can't delet last node by using below operation so we need to check it.
*******************************/
if(temp.next == null){
pre.next == null;
return list;
} else {
pre = tmp;
list.delete(tmp);
}
} else {
bitarray = bitarray | x;
pre = tmp;
tmp = tmp.next();
}
}
}
deleteNode(LinkedList list, Node node){
/************************************************************************************
We are copieng values from next node to current node, and will remove next node;
************************************************************************************/
Node tmp = node.next;
node.value = tmp.value;
node.next = tmp .next;
tmp.next == null;
tmp = null;
}
We can implement it by using a combination of HashMap and BST. HashMap will contain entry for key-value pair and BST only keys. All keys will be maintained in BST (sorted order).
lookup(Key): Make a simple lookup in to HashMap
rangeLookup() - It will be in two parts -
Keys[] rage(Key1, Key 2) from BST
Entry[] lookups(Keys[]) in HashMap
public static void main(String[] args) {
String arr[] = { "plates", "stop", "staple", "pots", "meat", "not", "pot", "team" };
HashMap<String, ArrayList<String>> hashMap = new HashMap<String, ArrayList<String>>();
for (int i = 0; i < arr.length; i++) {
int len = getSumOfChars(arr[i].toCharArray());
if (hashMap.get(len) != null)
hashMap.get(sorted).add(s);
else {
ArrayList<String> ts = new ArrayList<String>();
ts.add(s);
hashMap.put(len, ts);
}
}
System.out.println(hashMap);
}
public static int getSumOfChars(char[] chars){
int sum = 0;
for(int i = 0; i < chars.length; i++){
sum = sum + Charactor.getNumericValue(chars[i]);
}
return sum;
}
No!!. It is different , we are not using extra space O(n), but we are using O(1) space, simple integer as a bit array ...:)
- Ajeet August 22, 2013