找出数组中未出现的正整数

题目

给定一个无序数组，找出数组中未出现的正整数
arr=[-1,2,3,4]返回1
arr=[1,2,3,4]返回5

思路

用hash也可以做出来，但是空间复杂度很大，
该解是最优解，时间复杂度O(N)空间复杂度O(1)

设置2个变量l和r
l表示遍历到l位置时，已经收集到[1,l]的正整数，也表示左边界，初始值为0
r表示遍历该数组期望收集到[1,r]上面的数，也表示右边界，初始值为数组长度

遍历数组主要靠l和r来设置两端，直到他们相遇
遍历过程中，最好的情况是数组是1-r的集合，arr[i]的数字是i-1是最好的
对于每一个位置都期望得到是[l+1,r]中间的数字，因为对于l位置已经收集到了[1,l]的数组
对于不是期望区间的数组，r的期望区间会减小
对于arr[i]的数字不是i-1，但arr[i]是期望区间的，交换值为arr[i]-1的位置，这个意思是，只要不是期望数字，就一直交换，知道找到期望数字为止
比如最好的情况下，arr[2]=3,但是此时arr[2]=6,本来6应该出现在arr[5]的位置上的，因此就把arr中2和5位置的数字交换，再判断是不是3，知道找到3为止
3种情况

  • arr[i] <= l || arr[i] > r
    得到了期望区间之外的数字，最右边界损失把右边界
  • arr[i] 在[l+1,r]，但是不是i-1，交换a[i]-1与i的位置的值，
  • arr[i]收到重复值的时候，必然导致r的期望区间减小

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public int missNum(int[] arr) {
	int l = 0;
	int r = arr.length;
	while (l < r) {
		if (arr[l] == l + 1) {
			// 最好的时候，这一步要卸载最前面，否则会出现a[0]=1,匹配到arr[l] == arr[arr[l] - 1]导致错误
			l++;
		} else if (arr[l] > r || arr[l] <= l || arr[l] == arr[arr[l] - 1]) {
			// 出边界或者得到重复值
			swap(arr, l, --r);
		} else if (arr[l] != arr[arr[l] - 1]) {
			// 得到期望期间的值，但不是期望值 l+1，因此交换，知道得到期望值 l+1为止
			swap(arr, l, arr[l] - 1);
		}
	}
	return l + 1;
	
}
public void swap(int[] arr, int a, int b) {
	int tmp = arr[a];
	arr[a] = arr[b];
	arr[b] = tmp;
	return;
}