山东省住房建设厅网站安全处,网站百度云链接,天津视频网站开发团队,wordpress访问过的页码不变色题目描述
给你一个含 n 个整数的数组 nums #xff0c;其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字#xff0c;并以数组的形式返回结果。
示例 1#xff1a;
输入#xff1a;nums [4,3,2,7,8,2,3,1]
输出#xff1a;[5,6…题目描述
给你一个含 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.length1 n 1051 nums[i] n
**进阶**你能在不使用额外空间且时间复杂度为 O(n) 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。
解答
class Solution {
public:// vectorint findDisappearedNumbers(vectorint nums) {// 对元素值对应的下标的元素取负号表示为存在for(int i 0; i nums.size(); i){// 如 nums[3] 1, 则将 nums[1 - 1] 取负数// 即 nums[i] 0 表示 i 1存在if(nums[abs(nums[i]) - 1] 0) // 注意判断值可能被修改为负数了nums[abs(nums[i]) - 1] -nums[abs(nums[i]) - 1]; }vectorint res;for(int i 0; i nums.size(); i){if(nums[i] 0) res.push_back(i 1); }return res;}vectorint findDisappearedNumbers1(vectorint nums) {// 暴力法vectorint counters(nums.size() 1, 0);vectorint res;for(int num : nums){counters[num];}for(int i 1; i nums.size(); i){if(counters[i] 0) res.push_back(i);}return res;}
};
