星环科技2022秋招算法题1 | #序列找数#

解法一：双指针二分查找

因为每次mid查到当前位置和index匹配就把left指针移动到mid+1，表示left之前的元素都合法

当mid大于index的时候意味着在mid左边发生了跳位，导致跳位后的元素全都不合法，因此把right放在mid-1，表示right右边都是不合法的元素，要往左找到第一个非法元素

这样移动到最后，left保所有合法元素，right保所有非法元素，最后left和right会停在第一个非法元素上

因为第一个非法元素一定是跳了一位，其元素值本该为index，所以直接返回index，这就是丢失的值

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();       // 共有n个数
        int[] arr = new int[n];
        for (int i = 0; i < n; ++i) {
            arr[i] = in.nextInt();
        }

        Arrays.sort(arr);
        int left = 0;
        int right = arr.length;

        while (left < right) {
            int mid = (left + right) / 2;
            if (arr[mid] == mid) {   // 在右边
                left = mid + 1;
            } else if (arr[mid] > mid) {    // 在左边
                right = mid - 1;
            }
        }

        System.out.println(left);
    }
}

解法二：HashMap

原理：利用HashMap的containsKey方法。

将数组的每个数都存在map里，然后定义一个target，从0开始，如果这个target在nums中存在，那么containsKey返回true；

然后让target++继续遍历map。

直到map中没有target了，此时containsKey返回false，target就是缺失值

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            map.put(sc.nextInt(), 1);
        }
        int target = 0;
        while (map.containsKey(target)) {
            target++;
        }
        System.out.println(target);
    }
}