【数据结构】_时间复杂度相关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];}
}