[LeetCode] 41. First Missing Positive java

/**41. First Missing Positive * @param nums * @return 第一个缺少的正数 * O(n) */ public int firstMissingPositive(int[] nums) { int len = nums.length; if (nums == null || nums.length == 0) { return 1; } for (int i = 0; i < len; i++) { while (nums[i] != i+1) { if (nums[i] > nums.length || nums[i] <= 0 || nums[i] == nums[nums[i]-1]) break; int temp = nums[i]; nums[i] = nums[temp-1]; nums[temp-1] = temp; } } for (int i = 0; i < len; i++) { if (nums[i] != i+1) return i+1; } return nums.length+1; } //把元素放入正确的位置，例如1放在A[0]，2放在A[1]... //桶排序思想，每次当A[i]!= i的时候，将A[i]与A[A[i]]交换，直到无法交换位置。终止条件是 A[i]== A[A[i]]。