数组中重复的数字

1. 题目描述

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。

2. 思路

• map计数：使用LinkedHashMap计数同时保持插入顺序
• val作为index，对比找到所有数组中消失的数字.md，这道题找的是重复的数字而不是缺失的数字

3. 实现

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++
    //    这里要特别注意~返回任意重复的一个，赋值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)
    {
        //检查参数
        if (numbers == null || numbers.length == 0 || length <= 0 || duplication == null || duplication.length == 0)
        {
            return false;
        }
        //遍历把val：count存入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);
            }
        }
        //遍历map，如果count为1那么返回
        for (Map.Entry<Integer, Integer> entry : map.entrySet())
        {
            if (entry.getValue() > 1)
            {
                duplication[0] = entry.getKey();
                return true;
            }
        }

        return false;
    }
}

• go

//时间复杂度：O(N)
//空间复杂度：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. 原地Hash

func findRepeatNumber(nums []int) int {
    //原地Hash的思想
    for i := range nums {
        for nums[i] != i {
            val := nums[i]
            index := indexFor(val)
            // 如果val和i不相等，那么位置不正确，需要把该位置的val交换到下标为val的位置
            // 先看下下标为val的位置的元素是不是已经是val，是的话说明重复，返回之
            if nums[index] == val {
                return val
            }
            // 否则交换
            nums[index], nums[i] = nums[i], nums[index]
        }
    }
    return 0
}

func indexFor(val int) int {
    return val
}

4. 参考

• 数组中重复的数字_牛客网
• 剑指 Offer 03. 数组中重复的数字（哈希表 / 原地交换，清晰图解） - 数组中重复的数字 - 力扣（LeetCode）