Daily C/C++ 利用值域节省空间

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;
    }
}

理清这个思路，用一些技巧帮我们在数组中储存额外的信息，同时也不能影响原本数据的表达