Daily C/C++ 利用值域节省空间
这个文章内容会比较少,是我在做leetcode题中遇到的
但是无论如何也是新学习到的东西,所以这里简单记录一下
就是一个数组,叫我们找出其中任意一个重复的数
如果值域较大的话,我们可以用哈希表来解决
这道题有个特殊的点就是他的值域是小于给出数组大小的,这也启发了我们可以进行原地修改来帮我们记录信息
这里的技巧就是,对于当前扫描到的数x,我们去找数组中对应下标的位置nums[x]
,如果nums[x]
是正数,那么我们将它变成负数,否则我们就找到了一个重复的数
这里重点在于理清楚当前数x和nums[x]
的关系,nums[x]
的正负帮我们储存了”是否出现过x“这一信息,而对于nums[x]
本身的数值是没有关系的。我们取数的时候用绝对值就行
代码如下
for (int i = 0; i < nums.size(); i++) {
int cur = nums[i] < 0 ? -nums[i] : nums[i];
if (nums[cur] < 0) {
return cur;
} else {
nums[cur] *= -1;
}
}
理清这个思路,用一些技巧帮我们在数组中储存额外的信息,同时也不能影响原本数据的表达
文章评论