Ronzii's Blog

Just your average geek's blog

Finding duplicates in O(n)

Input: Given an array of n elements which contains elements from 0 to n-1, with any of these numbers appearing any number of times.

Goal : To find these repeating numbers in O(n) and using only constant memory space.

#include <iostream>
using namespace std;
void duplicates(int a[], int n)
{
    for (int i = 0; i < n; i++)
    {
        while(a[a[i]]!=a[i])
            swap(a[a[i]],a[i]);
    }
    for (int i = 0; i < n; i++)
        if (a[i] != i)
            cout<<a[i]<<" ";
}
int main()
{
    int x[] = {1, 2, 3, 1, 3, 0, 6};
    int n = sizeof x / sizeof x[0];
    duplicates(x, n);
    return 0;
}
Advertisements

March 30, 2012 Posted by | C++ | , , , , | Leave a comment