leetcode448. 找到所有数组中消失的数字

leetcode

题目描述

给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

示例 1：

输入：nums = [4,3,2,7,8,2,3,1] 输出：[5,6] 示例 2：

输入：nums = [1,1] 输出：[2]

提示：

n == nums.length 1 <= n <= 105 1 <= nums[i] <= n 进阶：你能在不使用额外空间且时间复杂度为 O(n) 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/find-all-numbers-disappeared-in-an-array 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

法1

排序
将数组进行排序,然后遍历排序好的数组,找出未出现的数据
使用原生的sort ints进行排序
如果没有缺少的数据则返回最后一个数据加1

• 时间复杂度(O(nlogn))
• 空间复杂度(O(1))

法2

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

法3

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

执行结果

法1

func findDisappearedNumbers(nums []int) []int {
 sort.Ints(nums)
    
 t:=0
 for i := 1; i < len(nums); i++ {
  if nums[i]-nums[i-1]>1 {
   for j := 1; j < nums[i]-nums[i-1]; j++ {
    nums[t]=nums[i-1]+j
    t++
   }
  }
 }
    if t == 0 {
  if nums[0] != 1 {
   return []int{1}
  }
  if nums[len(nums)-1] == 1 {
   return []int{nums[len(nums)-1]+1}
  }
 }
 return nums[:t]
}

执行用时： 44 ms , 在所有 Go 提交中击败了 74.04% 的用户 内存消耗： 7 MB , 在所有 Go 提交中击败了 95.03% 的用户 通过测试用例： 33 / 33