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