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

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

题目描述

找出数组中重复的数字。

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

示例 1：

输入： [2, 3, 1, 0, 2, 5, 3] 输出：2 或 3

限制：

2 <= n <= 100000

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

法1

方法1:
排序法:\

1. 先对数组数据进行排序,然后溢出遍历数组,相同的数据会同时出现,就可以判断相邻数据是否相同来判断该数是否重复 时间复杂度(O(nlogn)) 空间复杂度(O(1))

法2

方法2:
哈希表
通过建立哈希映射来判断数据的重复性 建立一个map[int]bool,key(int)储存出现的数据,value(bool)储存是否出现过,未出现就是开始的状态为false,当出现之后就变成true,当第二次出现的时候,判断value为true代表出现过,就直接返回该值.

if m[v] {//如果出现过
   return v//直接返回该值
  }
  m[v] = true//没出现过就变成出现过继续循环

时间复杂度(O(n))
其中n为输入数组nums的长度，因为它遍历整个数组并在最坏情况下执行n次操作。 空间复杂度(O(n))
因为它使用一个大小为n的哈希表来存储数字。在最坏情况下，哈希表将包含所有输入数字，因此空间复杂度为O(n)。

法3

时间复杂度(O()) 空间复杂度(O())

执行结果

哈希

// 方法2:哈希表
func findRepeatNumber2(nums []int) int {
 m := make(map[int]bool)
 for _, v := range nums {
  if m[v] {
   return v
  }
  m[v] = true
 }
 return 0
}

执行结果： 通过 显示详情 查看示例代码 添加备注

执行用时： 36 ms , 在所有 Go 提交中击败了 35.87% 的用户 内存消耗： 7.8 MB , 在所有 Go 提交中击败了 74.47% 的用户 通过测试用例： 27 / 27

排序

func findRepeatNumber(nums []int) int {
sort.Ints(nums)//数组排序
for i := 1; i < len(nums); i++ {
 if nums[i]==nums[i-1] {//判断是否相等
  return nums[i]
 }
}
return 0
}

执行用时： 44 ms , 在所有 Go 提交中击败了 9.66% 的用户 内存消耗： 7.7 MB , 在所有 Go 提交中击败了 93.22% 的用户\

总结

总体来说 排序空间上更好,哈希时间上更好.