【数据结构】_时间复杂度相关OJ（力扣版）
目录
1. 示例1：消失的数字
思路1：等差求和
思路2：异或运算
思路3：排序＋二分查找
2. 示例2：轮转数组
思路1：逐次轮转
思路2：三段逆置（经典解法）
思路3：开辟新数组
1. 示例1：消失的数字
题目链接：
面试题 17.04. 消失的数字 - 力扣（LeetCode）
思路1：等差求和
第一步：0—N利用求和公式计算总和，
第二步：减去数组中的所有元素的值，得到的差值即缺失的元素，
时间复杂度为O(N)；
实现程序如下：
int missingNumber(int* nums, int numsSize) {
int N=numsSize;
// 0~numsSize共numsSize+1个数字
int sum=(0+N)*(N+1)/2;
for(int i=0;i<numsSize;i++){
sum-=nums[i];
}
return sum;
}思路2：异或运算
第一步：用0与数组中所有的数据都异或一遍;
第二步：所得结果再与0—N之间的数字异或一遍；
因为异或与顺序无关，存在的数字都异或了两次，最终结果都是0（同0异1），只有那个0—N之间存在然而数组中不存在的数字经过两次异或后结果为1，这个数就是缺失的数字。
实现程序如下：
int missingNumber(int* nums, int numsSize) {
int x=0;
for(int i=0;i<numsSize;i++){
x^=nums[i];
}
for(int j=0;j<numsSize+1;j++){
x^=j;
}
return x;
}思路3：排序＋二分查找
第一步：将数组元素进行排序，降序升序均可，以升序为例；
第二步：按照0~N的顺序依次查找，若下一个数不等于上一个数+1，则下一个数字为消失的数字；
分析时间复杂度：冒泡排序O(N)＋二分查找log N 或 快排O(N)＋二分查找log N二者均不满足复杂度要求，故不做详细解释。
2. 示例2：轮转数组
题目链接：
189. 轮转数组 - 力扣（LeetCode）
思路1：逐次轮转
对于N个元素向右轮转k个位置的轮转次数分析：
若不考虑轮转的周期性，则时间复杂度为O(K*N)，（准确为O(K*(N-1))）
但由于数组长度定长，必然存在一些旋转的周期性问题。
真实旋转次数为k%=N，
最好的情况为旋转N的倍数次，即k%N==0，相当于没有旋转；
最坏的情况为k%N==N-1（量级为N），故时间复杂度为O(N^2)；
void rotate(int* nums, int numsSize, int k) {
k%=numsSize;
// 旋转k轮
while(k--){
// 旋转1轮
int tmp=nums[numsSize-1];
for(int i=numsSize-2;i>=0;i--){
nums[i+1]=nums[i];
}
nums[0]=tmp;
}
}存在问题：这种暴力求解的时间复杂度过高：
思路2：三段逆置（经典解法）
对于N个元素向右轮转k个位置的轮转，先将前n-k个逆置，再将后k个逆置，最后再整体逆置，即可达到预期轮转效果。此种情况下，时间复杂度为O(N)。（准确计算为O(2*N)）
实现程序如下：
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) {
k%=numsSize;
reverse(nums,0,numsSize-k-1);
reverse(nums,numsSize-k,numsSize-1);
reverse(nums,0,numsSize-1);
}思路3：开辟新数组
额外开辟一个数组，将nums数组后k个元素存放至arr数组前k个位置，将nums数组前numsSize-k个元素存放至arr数组后numsSize-k个位置，再将arr元素依次赋值给nums元素：
#include<string.h>
void rotate(int* nums, int numsSize, int k) {
int arr[numsSize];
k%=numsSize;
int n=numsSize;
memcpy(arr, nums+n-k,sizeof(int)*k);
memcpy(arr+k,nums,sizeof(int)*(n-k));
memcpy(nums,arr,sizeof(int)*n);
}注：若未采用memcpy，也可使用循环实现逐个拷贝：
void rotate(int* nums, int numsSize, int k) {
int arr[numsSize];
k%=numsSize;
int n=numsSize;
// 将nums数组后k个元素存放至arr数组前k个位置
for(int i=0;i<=k-1;i++){
arr[i]=nums[n-k+i];
}
// 将nums数组前n-k个元素存放至arr数组后n-k个位置
for(int j=0;j<=n-k-1;j++){
arr[k+j]=nums[j];
}
// 将arr元素依次赋值给nums元素
for(int x=0;x<=n-1;x++){
nums[x]=arr[x];
}
}