网站建设 不违背,wordpress引用fa图标,如何做网站经营性备案,wordpress文章内链目录
一、题目描述
二、题目分析
2.1 方法一
2.1.1 思路
2.1.2 代码
2.2 方法二
2.2.1 思路
2.2.2 代码
2.3 方法三
2.3.1 思路
2.3.2 代码
三、完整代码 一、题目描述
oj链接#xff1a;https://leetcode.cn/problems/missing-number-lcci 数组nums包含从0到n的…目录
一、题目描述
二、题目分析
2.1 方法一
2.1.1 思路
2.1.2 代码
2.2 方法二
2.2.1 思路
2.2.2 代码
2.3 方法三
2.3.1 思路
2.3.2 代码
三、完整代码 一、题目描述
oj链接https://leetcode.cn/problems/missing-number-lcci 数组nums包含从0到n的所有整数但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗 示例 1 输入[3,0,1] 输出2 示例 2 输入[9,6,4,2,3,5,7,0,1] 输出8 二、题目分析 此题目要求算法在O(N)时间内完成也就是说时间复杂度不超过O(N)我们要找出数组nums中缺少的数有以下几种办法
2.1 方法一
2.1.1 思路 方法一主要是通过求和相减找出0-n中缺失的那个数先将0到n之间的数相加求和然后依次减去数组中的每个数得到的就是缺失的那个数。 注意这里求0到n的数相加的和我们使用了等差数列的求和公式sum(和) (n1)*n/2. 方法一的时间复杂度是O(N)我们要将0到n的和依次减去数组中的元素所以在这里我们需要遍历一遍数组即执行n次循环所以时间复杂度是O(N)他的空间复杂度是O(1)这个算法只额外开辟了几个变量属于是常数阶用O(1)来表示空间复杂度。
2.1.2 代码
int missingNumberTwo(int* nums, int n)
{int sum n * (n 1) / 2;int i 0;for (i 0; i n; i){sum - nums[i];}return sum;
}
2.2 方法二
2.2.1 思路 方法二主要是通过异或找出0-n中缺失的那个数在之前的博客操作符详解中具体对异或进行了解释如果不太清楚可以去看看。 对于任何一个数和0异或得到的都是他本身一个数和自己异或得到的是0并且异或是满足交换律的因此根据这一规律我们就可以找到0-n中缺失的那个数先将定义一个变量x将他初始化为0让他先和数组中的每个数进行异或操作然后再与0到n的每个数进行异或操作如果某个数在数组中和0-n中都存在异或之后为0如果有单独的一个数只在0-n中存在而不在数组中异或之后也无法消去将0分别与数组中的数以及0-n之间的数异或最后得到的就是缺失的那个数。 方法二的时间复杂度是O(N)我们要将0分别与数组中的数以及0-n之间的数异或需要遍历一次数组和依次0-n之间的数即执行2n次循环所以时间复杂度是O(N)他的空间复杂度是O(1)这个算法只额外开辟了几个变量属于是常数阶用O(1)来表示空间复杂度。
2.2.2 代码
int missingNumberOne(int* nums, int n)
{int x 0;for (int i 0; i n; i){x ^ nums[i];}for (int i 0; i n 1; i){x ^ i;}return x;
}
2.3 方法三
2.3.1 思路 方法三主要是先对数组进行排序处理然后使用二分查找在这里对数组排序我们使用的是qsort库函数使用qsort库函数还要提供一个比较函数compar。 方法三的时间复杂度是O(N*logN)在这个算法中我们要求时间复杂度分开来看二分查找的时间复杂度是O(logN)qsort的时间复杂度是O(N*logN)按照大O的渐进表示法此算法的时间复杂度是O(N*logN)。 注意题目中要求时间复杂度不超过O(N)所以这个思路在力扣上不会通过仅仅提供一种参考思路。
2.3.2 代码
int compar(const void* p1, const void* p2)
{return *((int*)p1) - *((int*)p2);
}int missingNumberThree(int* nums, int n)
{qsort(nums, n, 4, compar);int i 0;for (i 0; i n; i){int exchange 1;int begin 0;int end n - 1;while (begin end){ int mid (begin end) / 2;if (i nums[mid])begin mid 1;else if (i nums[mid])end mid - 1;else{exchange 0;break;}}if (exchange 1){return i;}}
}
三、完整代码 这道题是属于oj类型的题目所以在拿到vs上编译的时候需要自己写一个主函数在这里我们提供一个完整的函数。
#define _CRT_SECURE_NO_WARNINGS 1
#includestdio.hint compar(const void* p1, const void* p2)
{return *((int*)p1) - *((int*)p2);
}int missingNumberOne(int* nums, int n)
{int x 0;for (int i 0; i n; i){x ^ nums[i];}for (int i 0; i n 1; i){x ^ i;}return x;
}int missingNumberTwo(int* nums, int n)
{int sum n * (n 1) / 2;int i 0;for (i 0; i n; i){sum - nums[i];}return sum;
}int missingNumberThree(int* nums, int n)
{qsort(nums, n, 4, compar);int i 0;for (i 0; i n; i){int exchange 1;int begin 0;int end n - 1;while (begin end){ int mid (begin end) / 2;if (i nums[mid])begin mid 1;else if (i nums[mid])end mid - 1;else{exchange 0;break;}}if (exchange 1){return i;}}
}int main()
{int nums[5] { 0 };int i 0;int n sizeof(nums) / sizeof(nums[0]);for (i 0; i n ; i){scanf(%d, nums[i]);}//1.异或int x missingNumberOne(nums, n);printf(%d\n, x);//2.求和再相减x missingNumberTwo(nums, n);printf(%d\n, x);//3.排序二分查找x missingNumberThree(nums, n);printf(%d\n, x);return 0;
}
