sathiyanannauniversity
BAN USERwe can solve the problem with help of hashmap or hashtable
1 loop through the array and put the element in the hashmap
2 if the entries is not already available . put the entry in hashmap and initialize
the count value to 1
3 if the entries is already available . just increment the count value.
print it if the count==1
Java Pseudocode
int[] arrContent={2,1,3,4,1,6,1,3,2};
HashMap<int,int> duplicateMap=new HashMap<int,in>();
for(int i=0;i<arrContent.length;i++) {
if(!duplicateMap.containtsKey(arrContent[i]) {
duplicateMap.put(arrContent[i],1);
}
else {
int count=duplicateMap.get(arrContent[i]);
if(count==1) {
System.out.println(" duplicate value is"+arrContent[i]);
}
duplicateMap.put(arrContent[i],++count);
}
}
sorry i forgot to put break statement within if block
- sathiyanannauniversity April 25, 2010Java Pseudocode
int[] arrContent={1,3,7,3,9,7,1};
// Papulate hash map content
HashMap<int,int> oddMap=new<int,int> HashMap();
for(int i=0;i<arrContent.length;i++) {
if(!oddMap.containKey(arrContent[i])) {
oddMap.put(arrContent[i],1);
}
else {
int count=oddMap.get(arrContent[i]);
oddMap.put(arrContent[i],++count);
}
}
// iterate through hashmap and find the value
Set set=oddMap.keySet();
Iterator it=set.iterator();
while(it.hasnext()) {
int element=it.next();
int countVal=oddMap.get(element)
if(countVal%2==1) {
System.out.println(" Element with the odd number of count"+element);
}
}
Java Pseudocode
int[] arrContent={1,3,7,3,9,7,1};
// Papulate hash map content
HashMap<int,int> oddMap=new<int,int> HashMap();
for(int i=0;i<arrContent.length;i++) {
if(!oddMap.containKey(arrContent[i])) {
oddMap.put(arrContent[i],1);
}
else {
int count=oddMap.get(arrContent[i]);
oddMap.put(arrContent[i],++count);
}
}
// iterate through hashmap and find the value
Set set=oddMap.keySet();
Iterator it=set.iterator();
while(it.hasnext()) {
int element=it.next();
int countVal=oddMap.get(element)
if(countVal%2==1) {
System.out.println(" Element with the odd number of count"+element);
}
}
we can solve the problem with the help of hashmap or hashtable aswell.
1 read through the area and keep the elements and its count in hashmap
2 the value is already available . increase the count value .
3 if it is not available . put entry in hashmap element with the count value 1
finally iterate through hashmap and check for entry for which odd number of count value.
so time complexity-o(n)
space complexity-o(n)
Reply to Comment
what if you declared array size 6 . you need to reallocate the memory right..?
- sathiyanannauniversity April 14, 2010that is it is runing in amortized constant time for insertion
- sathiyanannauniversity April 14, 2010ArrayList is the dynamic array which we are using in java. whenever the size of array exceeds the permissible limit. new array of double or 1.5 old size is allocated and elements from old array is copied. old array memory is freed. runing time of insertion in dynamic array is amortized constant time
- sathiyanannauniversity April 14, 2010
so time complexity is o(n)
- sathiyanannauniversity April 25, 2010space complexity o(n)