fd

dingjikerbo · dingjikerbo · commit d53f294ad545 · 2018-11-27T15:22:55.000+08:00
diff --git a/leetcode/solution/src/FirstMissingPositive.java b/leetcode/solution/src/FirstMissingPositive.java
@@ -6,7 +6,7 @@ public class FirstMissingPositive {
 
     public int firstMissingPositive(int[] nums) {
         for (int i = 0; i < nums.length; i++) {
-            while (nums[i] >= 1 && nums[i] <= nums.length && nums[nums[i] - 1] != nums[i]) {
+            while (nums[i] - 1 >= 0 && nums[i] - 1 < nums.length && nums[nums[i] - 1] != nums[i]) {
                 swap(nums, i, nums[i] - 1);
             }
         }
diff --git a/leetcode/src/Main.java b/leetcode/src/Main.java
@@ -4,24 +4,25 @@ public class Main {
 
     public static class Solution {
 
-        public int largestRectangleArea(int[] heights) {
-            int[] indexes = new int[heights.length + 1];
-            int top = -1, max = 0;
-
-            for (int i = 0; i <= heights.length; ) {
-                int height = i == heights.length ? 0 : heights[i];
-                if (top < 0 || height > heights[indexes[top]]) {
-                    indexes[++top] = i++;
-                } else {
-                    int k = heights[indexes[top--]];
-                    int left = top < 0 ? 0 : (indexes[top] + 1);
-                    max = Math.max(max, (i - 1 - left + 1) * k);
+        public int firstMissingPositive(int[] nums) {
+            for (int i = 0; i < nums.length; i++) {
+                while (nums[i] - 1 < nums.length && nums[i] - 1 >= 0 && nums[i] != nums[nums[i] - 1]) {
+                    swap(nums, i, nums[i] - 1);
                 }
             }
-
-            return max;
+            for (int i = 0; i < nums.length; i++) {
+                if (nums[i] != i + 1) {
+                    return i + 1;
+                }
+            }
+            return nums.length + 1;
         }
 
+        private void swap(int[] nums, int i, int j) {
+            int t = nums[i];
+            nums[i] = nums[j];
+            nums[j] = t;
+        }
     }
 
 

Original file line number	Diff line number	Diff line change
`@@ -6,7 +6,7 @@ public class FirstMissingPositive {`
`6`	`6`
`7`	`7`	`public int firstMissingPositive(int[] nums) {`
`8`	`8`	`for (int i = 0; i < nums.length; i++) {`
`9`		`- while (nums[i] >= 1 && nums[i] <= nums.length && nums[nums[i] - 1] != nums[i]) {`
	`9`	`+ while (nums[i] - 1 >= 0 && nums[i] - 1 < nums.length && nums[nums[i] - 1] != nums[i]) {`
`10`	`10`	`swap(nums, i, nums[i] - 1);`
`11`	`11`	`}`
`12`	`12`	`}`