深圳牌匾制作seo公司是什么意思
目录
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];}
}