【数据结构】时间复杂度---OJ练习题

目录

🌴时间复杂度练习

📌面试题--->消失的数字

题目描述

题目链接：面试题 17.04. 消失的数字

🌴解题思路

📌思路1：

malloc函数用法 

📌思路2：

📌思路3：

---

🌴时间复杂度练习

🙊 如果有不了解时间复杂度的请移步上一篇文章：【数据结构】初识

📌面试题--->消失的数字

题目描述

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

题目链接：面试题 17.04. 消失的数字

示例 1：

输入：

[3,0,1]

输出：

2

示例 2：

输入：

[9,6,4,2,3,5,7,0,1] 

输出：

8

🌴解题思路

📌思路1：

1.开辟一个额外的N+1个数的数组（即malloc一个额外N+1个数的数组），建立一个映射关系，，将数组的值全部初始化为-1

2.遍历这些数字，这个数是多少就写到数组的对应位置

3.再遍历一遍数组，哪个位置是-1，哪个位置的下表就是缺失的数字

因为malloc数组基本没有时间消耗，但是初始化时需要循环N+1次，填数字的时候也循环了N+1次，最后遍历时最坏也要循环N+1次，总共3N+3次，根据大O的渐进表示法就知道时间复杂度O(N)。

时间复杂度是：O(N)

代码展示：

int missingNumber(int* nums, int numsSize){
     int* p = (int*)malloc((numsSize+1) * sizeof(int));
     for(int i=0;i

本网站所收集的部分公开资料来源于AI生成和互联网，转载的目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。