寻找重复数

1. 题目描述

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，找出 这个重复的数 。

2. 思路

1. 思路一
   • 先排序
   • 遍历比较相邻的两个数是否相同
2. 思路二
   • map统计数量
3. 思路三
   • 原地Hash
4. 二分

3. 实现

3.1. 排序

import "sort"

//时间：O(nlogn)
//空间：O(1)
func findDuplicate(nums []int) int {
	sort.Ints(nums)
	for i := 0; i < len(nums)-1; i++ {
		if nums[i] == nums[i+1] {
			return nums[i]
		}
	}

	return 0
}

3.2. HashMap

//时间：O(n)
//空间：O(n)
func findDuplicate2(nums []int) int {
	m := make(map[int]int, 0)
	for _, num := range nums {
		m[num]++
	}
	for num, count := range m {
		if count >= 2 {
			return num
		}
	}

	return 0
}

3.3. 原地Hash

func findDuplicate(nums []int) int {
    for i := range nums {
        for {
            index := indexFor(nums[i])
            if index == i {
                break
            }
            if nums[index] == nums[i] {
                return nums[index]
            }
            nums[index], nums[i] = nums[i], nums[index]
        }
    }
    return 0
}

func indexFor(val int)int{
    return val
}

3.4. 二分

//二分
//时间：O(NlogN)
//空间：O(1)
func findDuplicate3(nums []int) int {
	left := 1
	right := len(nums) - 1
	for left < right {
		mid := left + (right-left)>>1

		cnt := getCnt(nums, mid)

		if cnt > mid {
			right = mid
		} else {
			left = mid + 1
		}

	}
	return left
}

func getCnt(nums []int, mid int) int {
	cnt := 0
	for _, num := range nums {
		if num <= mid {
			cnt++
		}
	}
	return cnt
}

4. 参考

• 287. 寻找重复数 - 力扣（LeetCode）