【刷题记录】——时间复杂度

本系列博客为个人刷题思路分享，有需要借鉴即可。

1.目录大纲：
在这里插入图片描述

2.题目链接：
T1：消失的数字：LINK
T2：旋转数组：LINK

3.详解思路：

T1：

思路1：先排序，再与正常的数字相比较即可。

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdlib.h>
#include<stdio.h>int int_cmp(const void* e1,const void* e2)
{return *(int*)e1 - *(int*)e2;
}int missingNumber(int* nums, int numsSize) 
{//先排序qsort(nums,numsSize,sizeof(int),int_cmp);//生成正常的数组与之比较int i = 0;int lose = 0;for (i = 0; i < numsSize+1; i++){if (i != nums[i]){lose = i;break;}}return lose;
}int main()
{int arr[9] = { 9,6,4,2,3,5,7,0,1 };int ret = missingNumber(arr, sizeof(arr)/sizeof(arr[0]));printf("%d\n", ret);return 0;
}

思路2：先把正常数组数字全部加起来，然后减去原数组的数字

int missingNumber(int* nums, int numsSize){//思路二：先加起来然后减去，即可得到消失的数字
int i = 0;
int lose = 0;
int sum = 0;
//加上0到numsSize全部的数字
for(i = 0;i<numsSize+1;i++)
{sum+=i;
}
//减去原数组0到numsSize的数字
for(i = 0;i<numsSize;i++)
{sum-=nums[i];
}
//得到消失的数字
lose = sum;
return lose;
}

思路3：异或运算
前提知识：
0 ^ X = X;//任何数字跟0异或都是原来的数
X ^ X = 0;//两个一样的数字进行异或得到的是0
X ^ Y ^ X = Y;//异或操作满足交换律

int missingNumber(int* nums, int numsSize){// //思路二：先加起来然后减去，即可得到消失的数字
// int i = 0;
// int lose = 0;
// int sum = 0;
// //加上0到numsSize全部的数字
// for(i = 0;i<numsSize+1;i++)
// {
//     sum+=i;
// }
// //减去原数组0到numsSize的数字
// for(i = 0;i<numsSize;i++)
// {
//     sum-=nums[i];
// }
// //得到消失的数字
// lose = sum;
// return lose;//思路三：异或操作
int i = 0;
int lose = 0;
//异或正常的数组
for(i = 0;i<numsSize+1;i++)
{lose^=i;
}
//异或原来的数组
for(i = 0;i<numsSize;i++)
{lose^=nums[i];
}
//返回
return lose;
}

T2：

思路1：借助一个变量一个一个挪动

void rotate(int* nums, int numsSize, int k) {int temp = 0;int i = 0;//旋转几次while (k--){//开始第一组挪动temp = nums[numsSize - 1];//先把最后一个数字放到临时变量中for (i = numsSize - 2; i >= 0; i--){nums[i+1] = nums[i];}//挪动数组往前一位nums[0] = temp;//把临时变量中的值放到数组第一个}
}int main()
{int arr[7] = { 1,2,3,4,5,6,7 };rotate(arr,7,3);int i = 0;for (i = 0; i < 7; i++){printf("%d ", arr[i]);}return 0;
}

思路2：一步到位，拷贝法

void rotate(int* nums, int numsSize, int k) {if(k>numsSize)k%=numsSize;//新数组，拷贝int arr[numsSize];int i = 0;for(i = 0;i<numsSize;i++){arr[i] = nums[i];}//覆盖原数组内容for(i = 0;i<k;i++){nums[k-1-i] = arr[numsSize-1-i];}for(i = 0;i<numsSize-k;i++){nums[k+i] = arr[i];}
}

思路3：逆置

void Reverse(int* nums,int left,int right){while(left<right){nums[left] = nums[left]^nums[right];nums[right] = nums[left]^nums[right];nums[left] = nums[left]^nums[right];left++;right--;}}void rotate(int* nums, int numsSize, int k) {if(k>numsSize)k%=numsSize;//逆置前半部分Reverse(nums,0,numsSize-k-1);//逆置后半部分    4         6Reverse(nums,numsSize-k,numsSize-1);//逆置整体Reverse(nums,0,numsSize-1);}