消失的数字，旋转数组（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);
}