3. 数组中重复的数字

题目链接

牛客网 (opens new window)

力扣 (opens new window)

题目描述

在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的，也不知道每个数字重复几次。请找出数组中任意一个重复的数字。

Input:
{2, 3, 1, 0, 2, 5}

Output:
2

解题思路

方法一：由于只需要找出数组中任意一个重复的数字，因此遍历数组，遇到重复的数字即返回。为了判断一个数字是否重复遇到，使用 map 存储已经遇到的数字，如果遇到的一个数字已经在 map 中，则当前的数字是重复数字。

package main

import (
	"fmt"
)

func findRepeatNumber(nums []int) int {
	m := make(map[int]int)
	for _, value := range nums {
		if _, ok := m[value]; ok {
			// 存在该数值
			return value
		} else {
			// 不存在
			m[value] = 1
		}
	}
	return -1
}

func main() {
	nums := []int{2, 3, 1, 0, 2, 5, 3}
	num := findRepeatNumber(nums)
	fmt.Println("重复的一个数字为: ", num)
}

执行用时 : 76 ms, 在所有 Go 提交中击败了 7.58% 的用户

内存消耗 : 9.1 MB, 在所有 Go 提交中击败了 100% 的用户

方法二：排序，看前后元素是否相等

package main

import (
	"fmt"
	"sort"
)

func findRepeatNumber(nums []int) int {
	// 对整型切片进行排序
	sort.Ints(nums)

	// 遍历切片, 与下一个数字重复就返回
	for i, numsSize := 0, len(nums); i < numsSize-1; i++ {
		if nums[i] == nums[i+1] {
			return nums[i]
		}
	}
	return -1
}

func main() {
	nums := []int{2, 3, 1, 0, 2, 5, 3}
	num := findRepeatNumber(nums)
	fmt.Println("重复的一个数字为: ", num)
}

执行用时 : 56 ms, 在所有 Go 提交中击败了 22.35% 的用户

内存消耗 : 6.9 MB, 在所有 Go 提交中击败了 100% 的用户

方法三：因为数组长度为 n, 且数字都在 0 ~ n-1 范围内，所以只需要判断下标 i 是否与 nums[i] 相等即可（如果都相等，说明没有重复元素）：

• i 与 nums[i] 相等，继续向下扫描
• i 与 nums[i] 不相等，先比较 nums[i] 与 nums[nums[i]] 的值：
  • nums[i] 与 nums[nums[i]] 相等，返回 nums[i]
  • nums[i] 与 nums[nums[i]] 不相等，交换 nums[i] 与 nums[nums[i]] ，一直重复

package main

import (
	"fmt"
)

func findRepeatNumber(nums []int) int {
    for i := 0; i < len(nums); i++ {
        for i != nums[i] {
            if nums[i] == nums[nums[i]] {
                return nums[i]
            }
            nums[i], nums[nums[i]] = nums[nums[i]], nums[i]
        }
    }
    return -1
}

func main() {
	nums := []int{2, 3, 1, 0, 2, 5, 3}
	num := findRepeatNumber(nums)
	fmt.Println("重复的一个数字为: ", num)
}

执行用时 : 40 ms, 在所有 Go 提交中击败了 95.89% 的用户

内存消耗 : 8.9 MB, 在所有 Go 提交中击败了 23.87% 的用户