[数据结构与算法]力扣 面试题 17.19. 消失的两个数字

题目

给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？

以任意顺序返回这两个数字均可。

示例

输入: [1]
输出: [2,3]

输入: [2,3]
输出: [1,4]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/missing-two-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法1：指针模拟

Java实现

class Solution {
    public int[] missingTwo(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);

        int flag = 1, i = 0, j = 0;
        int[] res = new int[2];

        while (flag <= n + 2) {
            if (i < n && flag != nums[i]) {
                res[j++] = flag++;
            } else if (i < n && flag == nums[i]) {
                i++;
                flag++;
            } else {
                res[j++] = flag++;
            }
        }
        return res;
    }
}

方法2：分组异或

Java实现