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

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

eg: 任意一个就行 — 那就最先找的

一看到重复元素 — 直接哈希表

方案1：哈希表

时间N
空间N

  1. class Solution:
  2.     def findRepeatNumber(self, nums: List[int]) -> int:
  4.         map_list = set()
  6.         for num in nums:
  7.             if num in map_list:
  8.                 return num
  9.             else:
  10.                 map_list.add(num)

执行用时：40 ms, 在所有 Python3 提交中击败了85.14%的用户
内存消耗：23.5 MB, 在所有 Python3 提交中击败了63.19%的用户

方案2：原地排序 相邻比较

时间复杂度：最差为N ，还有受排序算法的影响
空间复杂度：1 ，还有受排序算法影响

  1. class Solution:
  2.     def findRepeatNumber(self, nums: List[int]) -> int:
  4.         nums.sort()
  6.         for i in range(len(nums)):
  7.             if nums[i] == nums[i+1]:
  8.                 return nums[i]

执行用时：40 ms, 在所有 Python3 提交中击败了85.14%的用户
内存消耗：23.6 MB, 在所有 Python3 提交中击败了9.45%的用户

感觉可能是 排序算法的影响

Day4.2 剑指 Offer 53 - I. 在排序数组中查找数字 I

统计一个数字在排序数组中出现的次数
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2

简单题 我重拳出击 — 数组有序
没啥可说的： 代码不太好看，但是时间 N ，空间1 害行

  1. class Solution:
  2.     def search(self, nums: List[int], target: int) -> int:
  4.         #  防止空[] 输入
  5.         if  len(nums) == 0:
  6.             return 0
  8.         count = 0
  9.         for num in nums:
  10.             if num < target:
  11.                 continue
  12.             elif num == target:
  13.                 count +=1
  14.             else:
  15.                 return count
  17.         # 防止最后一个元素也是target
  18.         return count

执行用时：28 ms, 在所有 Python3 提交中击败了91.63%的用户
内存消耗：15.6 MB, 在所有 Python3 提交中击败了69.96%的用户

Day4.3 剑指 Offer 53 - II. 0～n-1中缺失的数字

在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字

比较简单 ，没啥可以说的 一次遍历即可

  1. class Solution:
  2.     def missingNumber(self, nums: List[int]) -> int:
  3.         for index,num in enumerate(nums):
  4.             if num != index:
  5.                 return index
  7.         # 前面都不缺 就返回最后一个数字的下一个
  8.         return len(nums)