数组中未出现的最小正整数

发表于 | 分类于 ，

数组中未出现的最小正整数

arr=[-1,2,3,4] 返回 1

arr=[1,2,3,4] 返回 5 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static int missNum(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int l = 0; //目前已收集  1 ~ l 上的数
        int r = arr.length; // 后续最优的情况下 能收集  1 ~ r 上的数
        while (l < r) {
            if (arr[l] == l + 1) {
                l++;
            } else if (arr[l] < l || arr[l] > r || arr[arr[l] - 1] == arr[l]) {
                r--;
            } else {
                swap(arr, l, arr[l] - 1);
            }
        }
        return l + 1;
    }

    public static void swap(int[] arr, int low, int high) {
        int temp = arr[low];
        arr[low] = arr[high];
        arr[high] = temp;
    }