成都科技网站建设找哪家,织梦瀑布流网站模板,厦门百度seo点击软件,51模板ppt题目
448找到所有数组中消失的数字.go
给你一个含 n 个整数的数组 nums #xff0c;其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字#xff0c;并以数组的形式返回结果。
示例 1#xff1a;
输入#xff1a;nums [4,3,2,7,8,2,…题目
448找到所有数组中消失的数字.go
给你一个含 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) 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。
解法
package mainimport fmt// 448找到所有数组中消失的数字.go
// 给你一个含 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) 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。// 使用 map 非常简单,但不满足进阶
func findDisappearedNumbers1(nums []int) []int {slice : make([]int, 0)mp : make(map[int]bool, len(nums))for _, val : range nums {mp[val] true}for i : 1; i len(nums); i {if _, ok : mp[i]; !ok {slice append(slice, i)}}return slice
}// 1. 范围为1到n,
// 2. 将每个数-1取模, 如果按顺序就得到该值应该在的index处, 将该index处的值n, 那么在该范围的值都应该大于n
// 3. 此时我们找出值小于n的index, 即为缺失的数字
// 时间复杂的O(n) 空间复杂度O(1)
func findDisappearedNumbers(nums []int) []int {var rst []intn : len(nums)for i : 0; i n; i {idx : (nums[i] - 1) % nnums[idx] nums[idx] n}for i : 0; i n; i {if nums[i] n { // 因为n也可能缺失,所以是小于等于rst append(rst, i1) // 该坐标值1 就是该值, 因为是1到n,而坐标从0开始}}return rst
}func main() {nums : []int{4, 3, 2, 7, 8, 2, 3, 1}fmt.Println(findDisappearedNumbers(nums))
}
