给定一个未排序的整数数组, 找出其中没有出现的最小的正整数.
示例 1:
输入: [1,2,0]
输出: 3
示例 2:
输入: [3,4,-1,1]
输出: 2
示例 3:
输入: [7,8,9,11,12]
输出: 1
说明:
你的算法的时间复杂度应为 O(n), 并且只能使用常数级别的空间.
链接: https://leetcode-cn.com/problems/first-missing-positive
- class Solution {
- public:
- int firstMissingPositive(vector<int>& nums) {
- // 这是看了解答后的代码 满足题意 但速度没提高太多
- int size = nums.size();
- int *numsHash;
- int size_hash = size +1;
- // 创建一个哈希表 初始化为 0
- numsHash = new int[size_hash]();
- // 遍历 nums 对于小于数组长度的元素在哈希表中打个标记
- // 对于比数组长度大的数据可以忽略, 因为第一个缺失的正数没这么大
- for (int i = 0; i <size; ++i)
- {
- if (nums[i]> 0 && nums[i] <size_hash)
- {
- numsHash[nums[i]] = 1;
- }
- }
- // 遍历哈希表 找出第一个没打标记的
- int *end_pos = numsHash + size_hash;
- for (int *p = numsHash + 1; p != end_pos; ++p)
- {
- if (*p == 0)
- {
- return p - numsHash;
- }
- }
- return size_hash;
- }
- int firstMissingPositiveNew(vector<int>& nums) {
- // 这是我自己想的答案, 不符合题目 O(n) 要求, 但排名也挺高
- // 排序 然后找出第一个大于 0 的数字
- // 顺序查找下去, 直到发现本元数比上一个元素大 1 就说明找到了
- sort(nums.begin(), nums.end());
- // 从 1 开始找出第一个不在数组里面的正数 慢
- //for (int i = 1; i <= INT_MAX; ++i)
- //{
- // if (!binary_search(nums.begin(), nums.end(), i))
- // {
- // return i;
- // }
- //}
- auto it = upper_bound(nums.begin(), nums.end(), 0);
- if (it == nums.end() || *it != 1) return 1;
- for (++it; it != nums.end(); ++it)
- {
- if ((*it - *(it - 1))> 1)
- {
- return *(it - 1) + 1;
- }
- }
- return *(it - 1) + 1;
- }
- };
执行结果:
通过
显示详情
执行用时 :4 ms, 在所有 cpp 提交中击败了 83.16% 的用户
内存消耗 :8.7 MB, 在所有 cpp 提交中击败了 73.72% 的用户
来源: http://www.bubuko.com/infodetail-3289825.html