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