题目描述
blablabla
样例
blablabla
算法1
$O(n)$
通过左右双指针,左侧有效区,右侧垃圾区;
时间复杂度
参考文献
JAVA 代码
public int firstMissingPositive(int[] arr) {
if(arr == null || arr.length == 0){
return 0;
}
int l = 0;
int r = arr.length;
while(l != r){
if(arr[l] == l + 1){
l++;
}else if(arr[l] <= l || arr[l] > r || arr[arr[l] - 1] == arr[l]){
swap(arr, l, --r);
}else{
swap(arr, l, arr[l] - 1);
}
}
return r + 1;
}
private void swap(int[] nums, int x, int y){
int temp = nums[x];
nums[x] = nums[y];
nums[y] = temp;
}