Duplicate Number in an Array

1. Problem Description

All numbers in an array of length n are in the range 0 to n-1. Some numbers are duplicated, but the number of duplicated values and their repetition counts are unknown. Find any duplicated number in the array. For example, for the length-7 array {2,3,1,0,2,5,3}, one corresponding output is the first duplicated number, 2.

2. Approach

• Map counting: use a LinkedHashMap to count while preserving insertion order
• Use val as the index. Compared with Find All Numbers Disappeared in an Array, this problem looks for duplicated rather than missing numbers

3. Implementation

3.1. Map

• java

public class 数组中重复的数字
{
    // Parameters:
    //    numbers:     an array of integers
    //    length:      the length of array numbers
    //    duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
    //                  Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
    //    Note: return any duplicated value by assigning it to duplication[0]
    // Return value:       true if the input is valid, and there are some duplications in the array number
    //                     otherwise false
    public boolean duplicate(int numbers[], int length, int[] duplication)
    {
        // Check parameters
        if (numbers == null || numbers.length == 0 || length <= 0 || duplication == null || duplication.length == 0)
        {
            return false;
        }
        // Traverse and store val:count in a LinkedHashMap
        Map<Integer, Integer> map = new LinkedHashMap<>();
        for (int number : numbers)
        {
            if (map.containsKey(number))
            {
                map.put(number, map.get(number) + 1);
            }
            else
            {
                map.put(number, 1);
            }
        }
        // Traverse the map and return when a duplicated count is found
        for (Map.Entry<Integer, Integer> entry : map.entrySet())
        {
            if (entry.getValue() > 1)
            {
                duplication[0] = entry.getKey();
                return true;
            }
        }

        return false;
    }
}

• go

// Time complexity: O(N)
// Space complexity: O(N)
func Duplicate(numbers []int, duplication *[1]int) bool {
	countMap := make(map[int]int, 0)
	for _, number := range numbers {
		countMap[number]++
	}

	for _, number := range numbers {
		if countMap[number] > 1 {
			duplication[0] = number
			return true
		}
	}
	duplication[0] = -1
	return false
}

3.2. In-place Hash

func findRepeatNumber(nums []int) int {
    // In-place hash idea
    for i := range nums {
        for nums[i] != i {
            val := nums[i]
            index := indexFor(val)
            // If val differs from i, it is in the wrong position and must be swapped into the position whose index is val
            // First check whether the element at index val is already val; if so, it is duplicated, so return it
            if nums[index] == val {
                return val
            }
            // Otherwise, swap
            nums[index], nums[i] = nums[i], nums[index]
        }
    }
    return 0
}

func indexFor(val int) int {
    return val
}

4. References

• Duplicate Numbers in an Array - NowCoder
• Sword Offer 03. Duplicate Number in an Array - LeetCode