消失的两个数字

面试题 17.19. 消失的两个数字

难度困难34

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

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

示例 1:

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

示例 2:

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

提示：

• nums.length <= 30000

原地hash

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

        int []res = new int[2];
        int cnt = 0;
        boolean n1 = false,n2 = false;
		
        // 对原数组原地hash
        for(int i=0;i<n;i++){
            int index = Math.abs(nums[i])-1;
            if(index < n){
                nums[index] = -nums[index];
            }else if(index==n){
                n1 = true;
            }else if(index==n+1){
                n2 = true;
            }
        }
		// 正数的位置的index就是消失的数字
        for(int i=0;i < n;i++){
            if(nums[i] > 0){
                res[cnt++] = i+1;
            }
        }
        // 如果消失的是大于n的数字，需要在这里处理
        if(!n1&&!n2){
            res[0] = n+1;
            res[1] = n+2;
        }else if(!n1){
            res[1] = n+1;
        }else if(!n2){
            res[1] = n+2;
        }

        return res;
    }
}

赏

谢谢你请我吃糖果

微信