这两道题很有意思,由于元素为1~n,因此每个元素的值-1(映射到0~n-1)就可以直接当做下标。这样将 nums 中对应下标的元素 *-1 以i表示 index+1 这个元素出现过了,能节省存储的空间。
448. Find All Numbers Disappeared in an Array
class Solution { public: vector<int> findDisappearedNumbers(vector<int>& nums) { for (int i=0;i<nums.size();++i){ int index=abs(nums[i])-1; if (nums[index]>0) nums[index]*=-1; } vector<int> res; for (int i=0;i<nums.size();++i){ if (nums[i]>0) res.push_back(i+1); } return res; } };
442. Find All Duplicates in an Array
class Solution { public: vector<int> findDuplicates(vector<int>& nums) { vector<int> res; for (int i=0;i<nums.size();++i){ int index=abs(nums[i])-1; if (nums[index]>0) nums[index]*=-1; else res.push_back(index+1); } return res; } };
LeetCode 448. Find All Numbers Disappeared in an Array & 442. Find All Duplicates in an Array