julianusti
4/15/2014 - 8:28 AM

Find duplicates in an array of integers: S = {0...n}. Complexity is equals to O(n)

Find duplicates in an array of integers: S = {0...n}. Complexity is equals to O(n)

        public static int[] FindDuplicates(int[] array, int range)
        {            
            if (range == 0)
            {
                throw new ArgumentOutOfRangeException("range", "Range must be more than 0.");
            }

            int[] dups = new int[range];
            int[] digitflags = new int[range];
            int dupsCount = 0;

            foreach (var number in array)
            {
                if (digitflags[number] <= 1) { digitflags[number]++; }

                if (digitflags[number] > 1)
                {
                    dups[number]++;
                    dupsCount++;
                }
            }

            return dupsCount == 0 ? null : dups;
        }