【数据结构】习题之消失的数字和轮转数组

👑个人主页：啊Q闻

🎇收录专栏：《数据结构》

🎉前路漫漫亦灿灿

前言

消失的数字这道题目我会和大家分享三种思路。

还有一道题目是轮转数组，，也会分享三种思路，大家感兴趣就看一看吧。

一.消失的数字

题目为：

思路：

思路一：因为该题目是从一个有序数组中找出一个消失的数字，所以我们可以先排序，然后一个个查找。

时间复杂度分析：该种方法的查找时间复杂度与所用排序方法有关，如果用冒泡排序，时间复杂度为： O（N^2),如果用qsort排序，时间复杂度为：O（N*logN)。

思路二：设置一个变量x先于0~n中所有值异或，然后再和数组中所有值异或，相同的值异或结果为0，所以剩余的值就是消失的数字。

时间复杂度分析：0~n要遍历n+1个值，然后再与数组中的n个值遍历。所以时间复杂度为n+(n+1)=2n+1,O(N)。

思路三：计算0~n个数的累加和，然后依次减去数组中的值。

时间复杂度分析：该方法首先计算0~n的累加和时，要遍历，然后减去数组中的值时，也要遍历。所以时间复杂度为：n+1+n=2n+1,O(N)。

代码实现：

思路二实现：

int missingNumber(int* nums, int numsSize)
{int n=numsSize;int x=0;for(int i=0;i<=n;i++)//先将x和0~n中所有数字进行异或{x^=i;}for(int j=0;j<n;j++)//再将上述与数组中所有数字进行异或{x^=nums[j];}return x;
}

过程分析：

示例数组：nums={3，0，1}

第一个循环中：x=0^0^1^2^3

第二个循环中：x=0^0^1^2^3^3^0^1==2

注意：利用位运算异或，相同数字异或结果为0，0与任何数字异或都为数字本身。

思路三实现：

int missingNumber(int* nums, int numsSize){int n=numsSize;int ret=n*(n+1)/2;//等差0~n的累积和for(int i=0;i<n;i++){ret-=nums[i];}return ret;
}

二.轮转数组

题目为：

思路：

思路一：暴力求解，每次挪动旋转一个，右移k次。

时间复杂度分析：最坏情况：当k=N-1时，即相当于数组要全部移动n-1次，时间复杂度为：N*(N-1)=N^2-N,即O（N^2 )。

思路二：三段逆置，即将数组分为两部分，每部分分别逆置，然后整体逆置。

示例：输入：nums=[1,2,3,4,5,6,7],k=3

输出：[5,6,7,1,2,3,4]

前n-k个逆置 4，3，2，1，5 ，6，7

后k个逆置 4，3，2，1，7，6，5

整体逆置 5，6，7，1，2，3，4

时间复杂度分析:看整体的移动情况：N+N=2N,即时间复杂度为：O(N)

思路三：利用memcpy实现

示例：输入：nums=[1,2,3,4,5,6,7],k=3

输出：[5,6,7,1,2,3,4]

1，2，3，4，5，6，7

5，6，7，1，2，3，4

时间复杂度分析：O(N)

代码实现：

思路二实现：

void Reverse(int *nums,int left,int right)
{while(left<right)//详解一{int tmp=0;tmp=nums[left];nums[left]=nums[right];nums[right]=tmp;++left;--right;}
}
void rotate(int* nums, int numsSize, int k) {k%=numsSize;//当轮转数组大于数组长度时，其相当于有数组长度未移动Reverse(nums,0,numsSize-k-1);Reverse(nums,numsSize-k,numsSize-1);Reverse(nums,0,numsSize-1);}

思路二详解：

详解一：

思路三实现：

void rotate(int* nums, int numsSize, int k) {k%=numsSize;int n=numsSize;int tmp[n];memcpy(tmp,nums+n-k,sizeof(int)*k);memcpy(tmp+k,nums,sizeof(int)*(n-k));memcpy(nums,tmp,sizeof(int)*n);//因为是反转nums数组，所以最后要返回去}