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

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

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         6
   Reverse(nums,numsSize-k,numsSize-1);
   //逆置整体
   Reverse(nums,0,numsSize-1);

    
}