题目一
给定一个整数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; }
运行结果如下
以上就是本篇博客的全部内容啦 由于博主才疏学浅 所以难免会出现纰漏 希望大佬们看到错误之后能够
不吝赐教 在评论区或者私信指正 博主一定及时修正
那么大家下期再见咯
