消失的数字
数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？
位运算异或解题
异或是相同为0，不同为1。这就可以推出x⊕0=x和x⊕x=0。然后看题，数组nums包含的是0-n的所有整数，其中缺了一个。那么多我取0异或上0-n的值，再异或上数组nums中的值，这也最后结果就可以得到缺少的那个值了。
为什么呢 ？取0进行异或是因为0异或任何数还是他本身，就像1乘上任何数还是他本身一样。然后我异或了0-n的所有值，就保证了0-n的每个值我都至少有一个了。然后我在异或上nums中的值，两个相同的值异或了就是0，最后剩下的值就是0-n加上nums只出现过一次的值。这一个值就只能来之0-n，而正好是nums中缺失的那个值。
int missingNumber(int* nums, int numsSize){ int xor = 0; int i; for(i = 0; i < numsSize; ++i) { xor ^= nums[i]; } for(i = 0; i <= numsSize; ++i) { xor ^= i; } return xor; }
数学公式解题
因为nums包含的是0-n中的值，仅差一个且不重复，那么我们可以把他看做是一个等差数列，求0-n的和，最后求出来的值减去nums中值的和就可以得到缺少的那个值了。
int missingNumber(int* nums, int numsSize){ int n = 0; for(int i = 0; i <= numsSize; ++i) { n += i; } for(int i = 0; i < numsSize; ++i) { n -= nums[i]; } return n; }
轮转数组
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
暴力穷举，直接旋转k次
void rotate(int* nums, int numsSize, int k) { while (k--) { int ret = nums[numsSize - 1]; int i; for (i = numsSize - 1; i > 0; i--) { nums[i] = nums[i - 1]; } nums[0] = ret; } }
空间换时间
新建一个变长数组（部分编译器不支持变长数组，所以可能会有些会报错，但是OJ是支持的，可以直接在OJ上使用），先将下标大于k的的项放入新数组，然后再把剩余的项按顺序放入新数组。最后用新数组中的值，按照下标顺序覆盖原数组的值即可。
void rotate(int* nums, int numsSize, int k) { int newArr[numsSize]; for (int i = 0; i < numsSize; ++i) { newArr[(i + k) % numsSize] = nums[i]; } for (int i = 0; i < numsSize; ++i) { nums[i] = newArr[i]; } }
newArr[(i + k) % numsSize] = nums[i];中%numsSize的原因是K值可能是大于这个数组长度的。
三步翻转法
先给这个数组分区，0-k和k-end，分别翻转0-k和k-end，最后翻转整个数组。整个数组在翻转时会变成逆序，但是在整个数组翻转前，已经分区进行翻转了，就相当于逆序又变成正序了，但是因为是分区翻转的，所以最后会达到轮转数组的效果。
//创建一个翻转函数，用来逆置数组 void reverse(int* nums, int begin, int end) { while (begin < end) { int tmp = nums[begin]; nums[begin] = nums[end]; nums[end] = tmp; begin++; end--; } } void rotate(int* nums, int numsSize, int k) { k = k % numsSize; reverse(nums, 0, numsSize - k - 1); reverse(nums, numsSize - k, numsSize - 1); reverse(nums, 0, numsSize - 1); }
