剑指offer 2.3.1-2.3.2 数组/字符串

之前一直是拿LCR来练，最近把剑指offer的实体书买了。边看边练。

关于数组

数组相关的题目主要涉及到了两个概念。

数组的寻址是O(1)的，所以可以把数组当作哈希表来用。

然而，这时候的key也只能是int。

具体到这一题的优化： JZ3 数组中重复的数字

本来我的解法是再创建一个哈希表。然而，考虑到数组中的元素只会存在于0～n-1之间，所以可以直接把数组当作哈希表来用。

它的核心便是尝试将对应的数字转移到对应的位置上。（例如，2应该在下标2的位置上）

如果该位置上已经存在了“正确的数”（也就是，已经存在了2），那么就说明这个数是重复的。

这个和用哈希的if num in num_set的本质是一样的，但是我们只使用了O(1)的空间。

使用广义的二分查找。

取取值的中点，随后计算小于等于中点的数的个数和大于中点的数的个数。如果小于等于中点的数的个数大于中点，那么重复的数在左边；否则在右边。

事实上就讲述了一个从右到左的操作。

对于一个定长的数组（字符串也是数组的一种），如果从左到右复制（例如说，替换不同长度的字符串的时候），会需要把后面的元素整块多次移动，复杂度会到O(n^2)。

这个时候，可以考虑从右到左复制。先扩张出足够的空间，然后准备一个读指针和一个写指针，从右到左复制。