题目

我的复述：
假设一个名为nums的数组里[2,3,1,0,2,5,3]，只需要写代码，找出重复的数字2或者3即可。

题解

Map

最常用，也是最容易想到的解法。

一次遍历，将扫描到数字做判断，如果可以在map中查到，就添加进去，否则返回这个数字，因为这个数字已经在map里存在了，属于重复数字。

//Go实现
func findRepeatNumber(nums []int) int {
    var nummap = make(map[int]bool)
    for _,num := range nums {
        if !nummap[num] {
            nummap[num] = true  //map中没有这个num
        } else {
            return num  //重复，直接返回
        }
    }

    return -1
}

leetcode-cn执行：

1
2
3

执行用时：
56 ms, 在所有 Go 提交中击败了8.84%的用户
内存消耗：8.9 MB, 在所有 Go 提交中击败了39.48%的用户

牛客网执行：

运行时间：3ms
超过100.00%用Go提交的代码
占用内存：832KB
超过100.00%用Go提交的代码

//java实现
class Solution {
    public int findRepeatNumber(int[] nums) {
        //HashSet的特点是不会存储重复元素
        //所以可以用HashSet来查找出重复的元素
        Set<Integer> dic = new HashSet<>();
        //遍历数组，设置此时遍历的元素为num
        for (int num : nums) {
            //如果发现dic中已经存储了num
            //那么说明找到了重复的那个元素
            if (dic.contains(num)) {
                //把num这个结果进行返回
                return num;
            } else {
                //否则，说明dic中还没有存储num
                dic.add(num);
            }
        }
        return -1;
    }
}

原地交换

遍历数组并通过交换操作，使元素的索引与值一一对应（即nums[i] = inums[i]=i）。因而，就能通过索引映射对应的值，起到与字典等价的作用。可以看这个题解

//Go
func findRepeatNumber(nums []int) int {
    i := 0
    for i < len(nums) {
        if nums[i] == i {
            i++
            continue
        }
        if nums[nums[i]] == nums[i] {
            return nums[i]
        }
        tmp := nums[i]
        nums[i] = nums[tmp]
        nums[tmp] = tmp
    }

    return -1
}

leetcode-cn执行：

1
2
3

执行用时：
40 ms, 在所有 Go 提交中击败了86.59%的用户
内存消耗：8.7 MB, 在所有 Go 提交中击败了89.50%的用户

不会飞的章鱼

剑指 Offer 03. 数组中重复的数字

题目

题解

Map

原地交换