leetcode之缺失的第一个正数
2019-11-16 16:01:04来源:博客园 阅读 ()
leetcode之缺失的第一个正数
给定一个未排序的整数数组,找出其中没有出现的最小的正整数。
示例 1:
输入: [1,2,0]
输出: 3
示例 2:
输入: [3,4,-1,1]
输出: 2
示例 3:
输入: [7,8,9,11,12]
输出: 1
说明:
你的算法的时间复杂度应为O(n),并且只能使用常数级别的空间。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/first-missing-positive
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
1 class Solution { 2 public: 3 int firstMissingPositive(vector<int>& nums) { 4 //这是看了解答后的代码 满足题意 但速度没提高太多 5 int size = nums.size(); 6 7 int *numsHash; 8 int size_hash = size +1; 9 10 //创建一个哈希表 初始化为0 11 numsHash = new int[size_hash](); 12 //遍历nums 对于小于数组长度的元素在哈希表中打个标记 13 //对于比数组长度大的数据可以忽略,因为第一个缺失的正数没这么大 14 for (int i = 0; i < size; ++i) 15 { 16 if (nums[i] > 0 && nums[i] < size_hash) 17 { 18 numsHash[nums[i]] = 1; 19 } 20 } 21 22 //遍历哈希表 找出第一个没打标记的 23 int *end_pos = numsHash + size_hash; 24 for (int *p = numsHash + 1; p != end_pos; ++p) 25 { 26 if (*p == 0) 27 { 28 return p - numsHash; 29 } 30 } 31 32 return size_hash; 33 } 34 35 int firstMissingPositiveNew(vector<int>& nums) { 36 37 //这是我自己想的答案,不符合题目O(n)要求,但排名也挺高 38 //排序 然后找出第一个大于0的数字 39 //顺序查找下去,直到发现本元数比上一个元素大1就说明找到了 40 sort(nums.begin(), nums.end());执行结果: 通过 显示详情 执行用时 :4 ms, 在所有 cpp 提交中击败了83.16%的用户 内存消耗 :8.7 MB, 在所有 cpp 提交中击败了73.72%的用户
//从1开始找出第一个不在数组里面的正数 慢 41 //for (int i = 1; i <= INT_MAX; ++i) 42 //{ 43 // if (!binary_search(nums.begin(), nums.end(), i)) 44 // { 45 // return i; 46 // } 47 //} 48 49 auto it = upper_bound(nums.begin(), nums.end(), 0); 50 51 if (it == nums.end() || *it != 1) return 1; 52 53 for (++it; it != nums.end(); ++it) 54 { 55 if ((*it - *(it - 1)) > 1) 56 { 57 return *(it - 1) + 1; 58 } 59 } 60 61 return *(it - 1) + 1; 62 } 63 };
原文链接:https://www.cnblogs.com/kingstarer/p/11870522.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- leetcode 反转链表 2020-06-06
- [题记-动态规划] 编辑距离 - leetcode 2020-04-06
- [题记]字符串转换整数-leetcode 2020-04-03
- [题记]有效括号的嵌套深度-leetcode 2020-04-01
- [题记-数学-面试题]约瑟夫环-leetcode 2020-03-30
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash