Create 41.缺失的第一个正数(困难).md

JavaCodeMing · JavaCodeMing · commit 85b272f12098 · 2020-08-23T23:04:23.000+08:00
diff --git a/Algorithm/41.缺失的第一个正数(困难).md b/Algorithm/41.缺失的第一个正数(困难).md
@@ -0,0 +1,46 @@
+```text
+��Ŀ: ����һ��δ�������������,�����ҳ�����û�г��ֵ���С��������
+    ʾ��1:
+        ����: [1,2,0]
+        ���: 3
+    ʾ��2:
+        ����: [3,4,-1,1]
+        ���: 2
+    ʾ��3:
+        ����: [7,8,9,11,12]
+        ���: 1
+    ��ʾ: ����㷨��ʱ�临�Ӷ�ӦΪO(n),����ֻ��ʹ�ó�������Ķ���ռ�
+1.˫ָ��:
+    [1]˼·:
+        (1)����δ����ֱ��Ѱ�Һ���,�������������,ֻҪʱ�临�Ӷ�С�ڻ����O(n)����;
+        (2)�������鳤�Ⱥͱ߽�����,�����鳤�ȵ���0�������һ��Ԫ�ش���1ʱ,ֱ�ӷ���1;
+        (3)ʹ��˫ָ��,����һ��ָ�뱣��ǰһ����������Ԫ��,�����ǰԪ�غ�ǰһ��Ԫ�ز�1,��˵��������������;
+        (4)���ǵ���ĿҪ����û�г��ֵ���С��������,���Ա���ʱֱ�ӹ��˵�С�ڵ���0��Ԫ��;
+        (5)���ǵ������п��ܴ�����ͬ��Ԫ��,����ָ���ӦԪ����ͬ������;
+    [2]ʵ��:
+        class Solution {
+            public int firstMissingPositive(int[] nums) {
+                Arrays.sort(nums);
+                if (nums.length==0 || nums[0] > 1) {
+                    return 1;
+                }
+                // ˫ָ��pre��i
+                int pre = 0;
+                for (int i = 0; i < nums.length; i++) {
+                    // ���˵�С�ڵ���0��Ԫ�غ������ظ���Ԫ��
+                    if (nums[i] <= 0 || nums[i]==pre) {
+                        continue;
+                    }
+                    if (nums[i] - pre == 1) {
+                        pre = nums[i];
+                    } else {
+                        return pre+1;
+                    }
+                }
+                return pre+1;
+            }
+        }
+    [3]���Ӷȷ���:
+        (1)ʱ�临�Ӷ�: O(N),NΪ���鳤��
+        (2)�ռ临�Ӷ�: O(1)    
+```

-Original file line number
+Diff line change
@@ @@ -0,0 +1,46 @@ @@
 +```text
 +题目: 给你一个未排序的整数数组,请你找出其中没有出现的最小的正整数
 +    示例1:
 +        输入: [1,2,0]
 +        输出: 3
 +    示例2:
 +        输入: [3,4,-1,1]
 +        输出: 2
 +    示例3:
 +        输入: [7,8,9,11,12]
 +        输出: 1
 +    提示: 你的算法的时间复杂度应为O(n),并且只能使用常数级别的额外空间
 +1.双指针:
 +    [1]思路:
 +        (1)由于未排序直接寻找很难,因此首先是排序,只要时间复杂度小于或等于O(n)即可;
 +        (2)考虑数组长度和边界条件,当数组长度等于0或数组第一个元素大于1时,直接返回1;
 +        (3)使用双指针,定义一个指针保存前一个遍历到的元素,如果当前元素和前一个元素差1,则说明是连续递增的;
 +        (4)考虑到题目要求是没有出现的最小的正整数,所以遍历时直接过滤掉小于等于0的元素;
 +        (5)考虑到数组中可能存在相同的元素,则当两指针对应元素相同则跳过;
 +    [2]实现:
 +        class Solution {
 +            public int firstMissingPositive(int[] nums) {
 +                Arrays.sort(nums);
 +                if (nums.length==0 || nums[0] > 1) {
 +                    return 1;
 +                }
 +                // 双指针pre和i
 +                int pre = 0;
 +                for (int i = 0; i < nums.length; i++) {
 +                    // 过滤掉小于等于0的元素和跳过重复的元素
 +                    if (nums[i] <= 0 || nums[i]==pre) {
 +                        continue;
 +                    }
 +                    if (nums[i] - pre == 1) {
 +                        pre = nums[i];
 +                    } else {
 +                        return pre+1;
 +                    }
 +                }
 +                return pre+1;
 +            }
 +        }
 +    [3]复杂度分析:
 +        (1)时间复杂度: O(N),N为数组长度
 +        (2)空间复杂度: O(1)
 +```