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

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

给你一个含 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) 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。

思路：

• 方法1：利用map统计数字是否出现过
• 方法2：本质上是把原数组上对应index的值取负来标识某个值是否出现过

时间复杂度：均为O(n)

空间复杂度：方法1 - O(n)，方法2 - O(1)

// // 方法1，利用map统计次数:
// 空间复杂度：O(N)
// func findDisappearedNumbers(nums []int) []int {
//     m := make(map[int]int)
 
//     for i := 0; i < len(nums); i++ {
//         m[nums[i]] += 1
//     }
 
//     res := make([]int, 0)
//     for i := 1; i <= len(nums); i++ {
//         if _, ok := m[i]; !ok {
//             res = append(res, i)
//         }
//     }
 
//     return res
// }
 
// 方法2，参考：https://www.bilibili.com/video/BV1L34y1j7Rp/?spm_id_from=333.337.search-card.all.click&vd_source=2c268e25ffa1022b703ae0349e3659e4
// 本质上是把原数组上对应index的值取负来标识某个值是否出现过
// 空间复杂度：O(1)
func findDisappearedNumbers(nums []int) []int {
    for i := 0; i < len(nums); i++ {
		nums[MyAbs(nums[i])-1] = (-1) * MyAbs(nums[MyAbs(nums[i])-1]) // 下标从0开始，所以要减一操作
	}
 
	res := make([]int, 0)
	for i := 0; i < len(nums); i++ {
		if nums[i] > 0 {
			res = append(res, i+1)
		}
	}
 
	return res
}
 
func MyAbs(a int) int {
	if a < 0 {
		a *= -1
	}
 
	return a
}