The program finds the non repeated number in a int
array. I am using a count
for the duplicates and making a Numcounts[]
to store the count values. I am assuming the array is sorted. Then I can check the Numcounts[]
for 1
, and that would be the non-repeating number. The complexity is \$O(n^2)\$.
Can you tell me how to do the same thing using hashmaps? I haven't used hashmaps and I know the complexity can be reduced to \$O(n))\$ using them.
#include<stdafx.h>
#include<stdio.h>
int main()
{
int n=6;
int * Numcounts = new int[n];
int count = 0;
int a[6] = {1,1,1,2,2,3}; // sort the array before proceeding.Because in the else part count is set to zero.
//If the array is unsorted then count will be reset in middle and will not retain the previous count.
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(a[i]==a[j])
{
count = count+1;
Numcounts[i] = count;
}
else{
count = 0;
}
}
}
}