数据结构初阶---复杂度的OJ例题

复杂度的OJ例题

一、消失的数字
- 1.思路一
- 2.思路二
- 3.思路三
二、旋转数组
- 1.思路一
- 2.思路二
- 3.思路三

一、消失的数字

数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(N)时间内完成吗？
链接：力扣：消失的数字

1.思路一

排序+遍历：如果下一个数据不等于上一个数据加1，那么下一个数据就是那个消失的数字。
时间复杂度：O（N*LogN）由于这个时间复杂度时间复杂度过高，本思路不再冗余，赘述。

2.思路二

利用等差数列公式：从0加到n，然后再减去这个数组中的所有数字，那么最终所得的差就是缺失的数字。
时间复杂度：O（N）
代码如下：

#include <stdio.h>
int missingNumber(int* nums, int numsSize)
{int N = numsSize;int ret = N * (N + 1) / 2;for (int i = 0; i < N; i++){ret -= nums[i];}return ret;
}int main()
{int nums[] = { 0,1,2,3,4,5,7,8,9,10 };int sz = sizeof(nums) / sizeof(nums[0]);int ret=missingNumber(nums,sz);printf("%d", ret);return 0;
}

3.思路三

单身狗思路：利用：按位异或运算符：^（相同为0，相异为1）任何数字和0 ^ 还等于它本身。首先我们要把一个完整的数组按位异或起来，然后再与题目中缺失一个数字的数组再进行按位异或，最终得到的结果就是消失的数字。
代码如下：

#include <stdio.h>
int missingNumber(int* nums, int numsSize)
{int N = numsSize;int x = 0;//第1个循环的目的:先把一个完整的数组:从0~n的所有数字全部按位异或起来存放在一个数字x中//注意：这里循环的终止条件是：<=N,(因为我们连N也要算上)for (int i = 0; i <= N; i++){x ^= i;}//第2个循环的目的:就是让一个完整的数组与缺失一个数字的数组进行按位异或，最终得到的结果就是那个消失的数字！//注意：这里循环的终止条件是：<N,(因为nums数组中确失一个数字)for (int i = 0; i < N; i++){x ^= nums[i];}return x;
}int main()
{int nums[] = { 0,1,2,3,4,5,7,8,9,10 };int sz = sizeof(nums) / sizeof(nums[0]);int ret=missingNumber(nums,sz);printf("%d", ret);return 0;
}

二、旋转数组

链接力扣：旋转数组

1.思路一

中规中矩：依次向左旋转K个数据
合计旋转：K%N次
时间复杂度：O（N^2）
空间复杂度：O（1）
因为时间复杂度超过限制，所以说不予实现。

2.思路二

核心思想：以空间换时间：我额外开辟一个数组，直接复制从k开始后面所有数据到前面，然后把复制n-k的数字放后面。
时间复杂度：O（N）
空间复杂度：O（N）
在这里插入图片描述
代码如下：

void rotate(int* nums, int numsSize, int k)
{int n = numsSize;int* tmp = (int*)malloc(sizeof(int) * n);k %= n;//一定别忘了k%n!memcpy(tmp, &nums[n - k], sizeof(int) * k);memcpy(&tmp[k], nums, sizeof(int) * (n - k));memcpy(nums, tmp, sizeof(int) * n);free(tmp);//一定别忘了Free！！！因为是动态开辟的空间
}int main()
{int nums[] = { 1,2,3,4,5,6,7 };int k = 0;printf("请输入你想要旋转的次数：");scanf("%d", &k);int sz = sizeof(nums) / sizeof(nums[0]);rotate(nums, sz, k);for (int i = 0; i < sz; i++){printf("%d ", nums[i]);}return 0;
}

3.思路三

数学思想:以k为划分界线，左边逆置，右边逆置，整体逆置。

在这里插入图片描述
代码如下：

//逆置函数
void Inversion(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)
{int n = numsSize;k %= n;Inversion(nums, 0, n - k - 1);//左边逆置Inversion(nums, n - k, n - 1);//右边逆置Inversion(nums, 0, n - 1);//整体逆置}int main()
{int nums[] = { 1,2,3,4,5,6,7 };int k = 0;printf("请输入你想要旋转的次数：");scanf("%d", &k);int sz = sizeof(nums) / sizeof(nums[0]);rotate(nums, sz, k);for (int i = 0; i < sz; i++){printf("%d ", nums[i]);}return 0;
}