287. 寻找重复数

图片.png

二分查找

  1. package main
  3. import (
  4.     "fmt"
  5.     "sort"
  6. )
  8. func findDuplicate1(nums []int) int {
  9.       flag :=make([]int,len(nums))
  10.       for i:=0;i<len(nums);i++{
  11.            if flag[nums[i]]==1{
  12.            return nums[i]
  13.          }
  14.          flag[nums[i]]=1
  15.       }
  16.       return -1
  17. }
  18. func findDuplicate2(nums []int) int {
  19.    sort.Ints(nums)
  20.    l :=0
  21.    r :=len(nums)
  22.    for l<r{
  23.         mid := l+(r-l)>>1
  24.         if nums[mid]>mid{
  25.             l =mid+1
  26.      }else {
  27.          r =mid
  28.      }
  29.    }
  30.    return l
  31. }
  32. func findDuplicate(nums []int) int {
  33.     sort.Ints(nums)
  34.     for i := 0; i < len(nums); i++ {
  35.         if nums[i] == nums[i+1] {
  36.             return nums[i]
  37.         }
  38.     }
  39.     return 0
  40. }
  43. func main() {
  44.     //1 2,2,3,4
  45.     fmt.Println(findDuplicate([]int{1,3,4,2,2}))
  46.     fmt.Println(findDuplicate([]int{3,1,3,4,2}))
  47. }