Find the non repeating number in the integer array

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
#include

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

If the array is sorted you do not need hashmaps to achieve O(n). If you have a random/unsorted array you can use hashmaps to achieve the purpose, see Paulo's answer for that. Note that sorting requires O(n log(n)).

If you want to know how often each integer is in the original collection you will also need hashmaps, but if you only want to know a nonduplicate number in a sorted array the following code will work:

// N is the number of ints in sorted
int nonduplicate(int sorted[], const int N){
    //To prevent segfaulting when N=1
    if(N==1){ return sorted[0]; };

    for(int i=0;i < N-1;i++){
        if(sorted[i] == sorted[i+1]){
            // Next number in collection is the same so the current number is not unique
            // Set i to the first location of the next different number
            do{
                i++;
            }while(i < N-1 && sorted[i] == sorted[i+1]);
        }else{
            // The next number is different so the current is unique
            return sorted[i];
        }
    }
    // Is the last number unique?
    if(sorted[N-1] != sorted[N-2]){
        return sorted[N-1];
    }
    // No unique numbers
    return -1;    // Or some other value you reserve for it
}

Note that this code is faster because it doesn't have the overhead of a hashmap and may stop before traversing the whole array, but does have the same big-O limit.

StackExchange Code Review Q#1434, answer score: 7