时空复杂度题目讲解
时空复杂度题目讲解
- 题目一
- 题目二
- 题目三
- 解法一
- 解法二
- 解法三
- 解法四
- 题目四
- 解法一
- 解法二
- 解法三
题目一
给定一个整数sum，从有N个有序元素的数组中寻找元素a，b，使得a+b的结果最接近sum，最快的平均时间复杂度是（ ）
作业内容
A.O(n)
B.O(n^2)
C.O(nlogn)
D.O(logn)
此题目中，数组元素有序，所以a,b两个数可以分别从开始和结尾处开始搜，根据首尾元素的和是否大于sum,决定搜索的移动，整个数组被搜索一遍，就可以得到结果，所以最好时间复杂度为n
题目二
int** fun(int n) {
int ** s = (int **)malloc(n * sizeof(int *));
while(n--)
s[n] = (int *)malloc(n * sizeof(int));
return s;
}
要求下面整个函数的空间复杂度
首先它定义了一个二级指针s
然后在下面 首先循环n次
每一次都创建一个指针 指向n个int大小的空间
所以说它的空间复杂度是1 +2 +3 + …+n
实际上的空间复杂度是O（n^2）
题目三
找到消失的数字
数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？
注意：本题相对书上原题稍作改动
示例 1：
输入：[3,0,1]
输出：2
示例 2：
输入：[9,6,4,2,3,5,7,0,1]
输出：8
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/missing-number-lcci
对于一个有序数组 要求我们找到其中缺失的数字
这道题目 我们至少有四种解法
解法一
我们将这个数组进行一个快速排序 然后看看每一个数字是否等于对应的i就可以
这样解法的时间复杂度是（NlogN） 空间复杂度是O（1）
代码表示如下
int cmp(const void* e1, const void* e2)
{
return *(int*)e1 - *(int*)e2;
}
int main()
{
int i = 0;
int arr[] = { 0, 1, 4, 3, 7, 6, 5, 9, 8 };
qsort(arr, 9, 4, cmp);
for ( i = 0; i < 9; i++)
{
printf("%d ", arr[i]);
}
for ( i = 0; i < 9; i++)
{
if (arr[i]!=i)
{
printf("\n消失的数字是%d", i);
break;
}
}
return 0;
}
这样子我们就可以成功找到消失的数字啦
运行效果如下
解法二
我们将1~sum的所有数字相加
之后再将数组中的所有元素相加
两者相减 就是消失的那个数字
此种解法的时间复杂度是O（N） 空间复杂度是O(1)
代码和表示结果如下
解法三
我们创建一个新数组 将这些数据依次填入数组中
哪个数组的元素未被赋值 那么消失的数字就是这个数
int main()
{
int i = 0;
int arr1[10] = { 0 };
for ( i = 0; i <= 9; i++)
{
arr1[i] = -1;
}
int arr[] = { 0, 1, 4, 3, 7, 6, 5, 9, 8 };
for (i = 0; i < 9; i++)
{
int tmp = 0;
tmp = arr[i];
arr1[tmp] = tmp;
}
for ( i = 0; i < 9; i++)
{
if (arr1[i]==-1)
{
printf("消失的数字是%d", i );
break;
}
}
return 0;
}
这个解法的时间复杂度是O（N） 空间复杂度也是O（N）
解法四
我们都知道异或这个操作符 相同为0 想异为1
并且两个相同的数字异或的结果为0
0与任何数异或都等于它本身
那这样子我们的思路就很清晰了 创建一个数字ret 使用这个数字异或0~n所有数字
之后再异或数组中的所有数 这样子我们就能得到消失的数啦
int main()
{
int ret = 0;
int i = 0;
int arr[] = { 0, 1, 4, 3, 7, 6, 5, 9, 8 };
for ( i = 0; i <= 9; i++)
{
ret ^= i;
}
for ( i = 0; i < 9; i++)
{
ret ^= arr[i];
}
printf("消失的数字是%d", ret);
return 0;
}
题目四
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof
解法一
这里我们第一时间想到的是排序之后看看和前面一个数 后面一个数比较 如果不同就输出它
可惜这一题的时间复杂度要求是O（N）直接毙掉所有的排序方法
解法二
我们可以将一个数组中所有元素设置为0 然后使用数组中的数字异或它们对应大小的位数
但是这个方法要创建一个数组 空间复杂度为O（N） 毙掉
解法三
对于这个数组 我们先将整个数组进行异或得到这两个数的异或结果
然后将这个数组进行分组
注意 这里难点来了 怎么分组？
我们可以找到这个数异或结果为1的位数（说明这两个数在这个位上不同）
那么我们就按照这个位来分组 1的一组 0的一组
它们两组自身异或 就能得到两个不同的数
这两个数就是我们要找的数
int main()
{
int nums[8] = {1, 2, 10, 4, 1, 4, 3, 3};
int* arr = (int*)malloc(8);
int ret = 0;
int pos = 0;
int i = 0;
// 全部异或得到一个数
for (i = 0; i < 8; i++)
{
ret ^= nums[i];
}
// 找到1的位数
for ( i = 0; i < 32; i++)
{
if ((ret >> i) & 1 == 1)
{
pos = i;
break;
}
}
// 按照位数来分组
int num1 = 0;
int num2 = 0;
for ( i = 0; i < 8; i++)
{
if ((nums[i] >> pos) & 1 == 1)
{
num1 ^= nums[i];
}
else
{
num2 ^= nums[i];
}
}
// 将num1 num2放到数组中输出
// 这里我就直接打印了
printf("%d %d", num1, num2);
arr[0] = num1;
arr[1] = num2;
free(arr);
arr = NULL;
return 0;
}
运行结果如下
以上就是本篇博客的全部内容啦 由于博主才疏学浅 所以难免会出现纰漏 希望大佬们看到错误之后能够
不吝赐教 在评论区或者私信指正 博主一定及时修正
那么大家下期再见咯