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

题意

一个所有数都在0~n之间的存在重复的数组，任意找出一个重复的数。

题解

思路：遍历数组，利用所有数都在0~n之间这一特点，将下标与值对应进行置换，下标不等于值则将值置换到对应下标，如果出现置换的时候已经存在对应值和下标的情况，则说明是重复的数，返回即可。

  • 时间复杂度：最坏情况下需要尝试n次，O（n）

  • 空间复杂度：原地置换，不需要多余空间，只需要常数等级空间，O（1）

    1. func findRepeatNumber(nums []int) int {
    2.   for i := 0; i < len(nums); i++ {
    3.       for i != nums[i] {
    4.           if nums[nums[i]] == nums[i] {
    5.               return nums[i]
    6.           }
    7.           nums[nums[i]], nums[i] = nums[i], nums[nums[i]]
    8.       }
    9.   }
    10.   return -1
    11. }

    结果：

  • 执行用时：36 ms, 在所有 Go 提交中击败了97.08%的用户

  • 内存消耗：8.7 MB, 在所有 Go 提交中击败了74.13%的用户