消失的数字，旋转数组（leetcode 一题多解）
目录
一、消失的数字
思路一（暴力求解）代码实现：
思路二（数列的思想）代码实现：
思路三（异或的运用）代码实现：
二、轮转数组
思路一（暴力求解）代码实现：
思路二使用额外的空间（以空间换时间）代码实现：
思路三（三步逆置）
一、消失的数字
思路如下图：
思路一（暴力求解）代码实现：
排序好后一一查找。
此处不建议使用该方法，因为时间复杂度过大。
int missingNumber(int* nums, int numsSize)
{int i = 0;int j = 0;int flag = -1;//利用冒泡排序思想进行排序for (i = 0; i < numsSize - 1; i++){for (j = 0; j < numsSize - 1 - i; j++){if (nums[j] > nums[j + 1]){int tmp = nums[j];nums[j] = nums[j + 1];nums[j + 1] = tmp;}}}//一个个查找for (i = 0; i < numsSize; i++){if (i != nums[i]){flag = i;break;}}return i;
}
思路二（数列的思想）代码实现：
此处代码就开始简化了：时间复杂度为O(N)，先用上等差数列的公式求前num个数字之和，再一一减去nums数组中的元素，最后得到的就是消失的数字！
int missingNumber(int* nums, int numsSize)
{int i=0;int sum=0;//前numsSize个数字相加，等差数列求和sum = (numsSize+1)*numsSize/2;//减去nums数组中的所有值的和for(i=0;i<numsSize;i++){sum-=nums[i];}return sum;
}思路三（异或的运用）代码实现：
利用了异或操作符
首先讲解一下这个操作符（^）：
这个操作符是对二进制来用的，相同为零相异为一
这个操作符有几个特点
1.n^0 = n
2.n^n = 0
3.满足交换律,如：(a^b) ^ c =a^（b^c）
如果想知道更多操作符的使用请移步到：操作符（笔记）-CSDN博客
思路:用0先跟0~numsSize中数据异或，再跟nums数组中所有元素异或，最后的值就是所要找的值
效果如下：
0^1^2^...中间有消失的数...^n ^1^2^...中间消失的数不在这里...^n = 0^中间有消失的数 =
中间有消失的数
int missingNumber(int* nums, int numsSize)
{int x = 0;int i = 0;//先跟0-numsSize中数据异或for (i = 1; i <= numsSize; i++){x = x ^ i;}//跟nums数组中数据异或for (i = 0; i < numsSize; i++){x = x ^ nums[i];}return x;}二、轮转数组
思路如下图所示
思路一（暴力求解）代码实现：
void rotate(int* nums, int numsSize, int k) {//如果k>=numsSize,则k=k%numsSize，减少循环次数if (k >= numsSize){k %= numsSize;}//轮转的次数for (int j = 1; j <= k; s++){//记录数组最后一个元素的值int tmp = nums[numsSize-1];//每一次的轮转数组的变化for (int i = numsSize - 1; i > 0; i--){nums[i] = nums[i - 1]; }//把记录下来的值赋给数组首元素nums[0] = tmp;}
}思路二使用额外的空间（以空间换时间）代码实现：
牺牲存储空间为代价，直接在栈上开辟一块新的存储空间
void rotate(int* nums, int sz, int k)
{//开辟与nums数组一样大小的空间int* tmp = (int*)malloc(sizeof(int) * sz);int i = 0;//如果k>=size,则k=k%size，减少循环次数if (k >= sz){k %= sz;}//先把后sz-k-1个元素拷贝到tmp中去for (i = 0; i < k; i++){tmp[i] = nums[sz - k + i];}//再把前k-1个元素拷贝到tmp中去for (i = 0; i < sz-k; i++){tmp[k+i] = nums[i];}//最后，把tmp的内容拷贝到nums中去for (i = 0; i < sz; i++){nums[i] = tmp[i];}
}思路三（三步逆置）
如果k>=numsSize时，取余数
因为，逆置8次和逆置1次效果是相同的
void reverse(int* nums, int left, int right) {while (left < right) {int tmp = nums[left];nums[left] = nums[right];nums[right] = tmp;left++;right--;}
}void rotate(int* nums, int numsSize, int k) {if(k>=numsSize){k %= numsSize; // 如果k大于等于数组长度，先对k取余}reverse(nums, 0, numsSize - k - 1);//注意控制下标reverse(nums, numsSize - k, numsSize - 1);reverse(nums, 0, numsSize - 1);
}