旋转数组
消失的数字
**
1.旋转数组
给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]
示例 2:
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]
提示：
1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
0 <= k <= 105
**
思路一：
1.前n-k个元素逆置
2.后k个元素逆置
3.最后进行整体的逆置
void reverse(int* nums, int left, int right) { while (left< right) { int temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; ++left; --right; } } if (k > numsSize) { k %= numsSize; } reverse(nums, 0, numsSize - 1); reverse(nums, 0, k - 1); reverse(nums, k, numsSize - 1); }
复杂度分析
时间复杂度：O(n)O(n)，其中 nn 为数组的长度。每个元素被翻转两次，一共 nn 个元素，因此：
总时间复杂度为 O(2n)=O(n)O(2n)=O(n)。
空间复杂度：O(1)O(1)。
思路二：
1.先创建一个新的数组
2.把后k个数放到新数组
3.在把前k个数向后移动
void rotate(int* nums, int numsSize, int k) { k %= numsSize; //变长数组 int temp = nums[numsSize]; //把后k个元素拷贝到前面 int j=0; for(int i= numsSize - k; i<numsSize ; i++) { temp[j] = nums[i]; ++j; } //把前n-k个拷贝到后面 for(int i= 0; i<numsSize-k ; i++) { temp[j] = nums[i]; ++j; } //拷贝回去 for(int i= 0; i<numsSize ; i++) { temp[] = nums[i]; } }
这里使用malloc来创建新数组的话也可以，只是不能调试而已
复杂度分析
空间复杂度： O(n)
时间复杂度： O(n)O(n)，其中 nn 为数组的长度
**
2.消失的数字
数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？
示例 1：
输入：[3,0,1]
输出：2
示例 2：
输入：[9,6,4,2,3,5,7,0,1]
输出：8
思路一：
数学
将从 0 到 n的全部整数之和先计算出来，接着我们去遍历数组，用得到的和减去数组中的元素，便可得到我们需要的数
int missingNumber(int* nums, int numsSize){ int n=numsSize; int ret=n*(n+1)/2; for(int i=0; i<numsSize; i++) { ret-=nums[i]; } return ret;
复杂度分析
时间复杂度：O(n)，其中 n是数组 nums 的长度。需要 O(1)的时间计算从 0 到 nn的全部整数之和以及需要 O(n) 的时间计算数组 nums 的元素之和。
空间复杂度：O(1)
思路二：
数组 nums 中有 n个数，在这 n个数的后面添加从 0 到 n 的每个整数，则添加了 n+1个整数，共有 2n+1个整数。
在 2n+1 个整数中，消失的数字只在后面 n+1 个整数中出现一次，其余的数字在前面 n 个整数中（即数组中）和后面 n+1个整数中各出现一次，即其余的数字都出现了两次。
根据出现的次数的奇偶性，可以使用按位异或运算得到消失的数字。按位异或运算 \oplus⊕ 满足交换律和结合律，且对任意整数x 都满足 x⊕x=0 和 x⊕0=x。
由于上述 2n+12n+1 个整数中，消失的数字出现了一次，其余的数字都出现了两次，因此对上述 2n+1个整数进行按位异或运算，结果即为消失的数字
int missingNumber(int* nums, int numsSize){ int n=numsSize; int x=0; for(int i=0; i<numsSize; i++) { x^=nums[i]; } for(size_t j=0; j<n+1; j++) { x^=j; } return x; }
复杂度分析：
时间复杂度：O(n)，其中 n是数组 nums 的长度。需要对 2n+1个数字计算按位异或的结果。
空间复杂度：O(1)
**
