Skip to content

Files

Latest commit

c29b144 · May 17, 2024

History

History
208 lines (163 loc) · 4.2 KB

README.md

File metadata and controls

208 lines (163 loc) · 4.2 KB
comments difficulty edit_url
true
困难

English Version

题目描述

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

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

示例 1:

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

示例 2:

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

提示:

  • nums.length <= 30000

解法

方法一:位运算

利用位运算的性质:

  1. 对于任何数 x ,都有 x x = 0
  2. 异或运算满足结合律,即 ( a b ) c = a ( b c )
  3. lowbit 运算获取最低一位的 1 及其后面的所有 0 ,公式为 lowbit(x) = x & (-x)

我们将 nums 中所有数进行异或到 x ,再将 [ 1 , 2. . n ] 的所有数也异或到 x 。得到的 x 是两个缺失的正整数的异或和。

然后我们运用 lowbit 获取最低一位的 1 ,那么这两个缺失的正整数在这一位上必然一个为 1 ,一个为 0 。我们据此进行分组异或。最终得到两个缺失的正整数 a b

时间复杂度 O ( n ) ,空间复杂度 O ( 1 ) 。其中 n 为数组长度。

Python3

class Solution:
    def missingTwo(self, nums: List[int]) -> List[int]:
        n = len(nums) + 2
        xor = 0
        for v in nums:
            xor ^= v
        for i in range(1, n + 1):
            xor ^= i

        diff = xor & (-xor)
        a = 0
        for v in nums:
            if v & diff:
                a ^= v
        for i in range(1, n + 1):
            if i & diff:
                a ^= i
        b = xor ^ a
        return [a, b]

Java

class Solution {
    public int[] missingTwo(int[] nums) {
        int n = nums.length + 2;
        int xor = 0;
        for (int v : nums) {
            xor ^= v;
        }
        for (int i = 1; i <= n; ++i) {
            xor ^= i;
        }
        int diff = xor & (-xor);
        int a = 0;
        for (int v : nums) {
            if ((v & diff) != 0) {
                a ^= v;
            }
        }
        for (int i = 1; i <= n; ++i) {
            if ((i & diff) != 0) {
                a ^= i;
            }
        }
        int b = xor ^ a;
        return new int[] {a, b};
    }
}

C++

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int n = nums.size() + 2;
        int eor = 0;
        for (int v : nums) eor ^= v;
        for (int i = 1; i <= n; ++i) eor ^= i;

        int diff = eor & -eor;
        int a = 0;
        for (int v : nums)
            if (v & diff) a ^= v;
        for (int i = 1; i <= n; ++i)
            if (i & diff) a ^= i;
        int b = eor ^ a;
        return {a, b};
    }
};

Go

func missingTwo(nums []int) []int {
	n := len(nums) + 2
	xor := 0
	for _, v := range nums {
		xor ^= v
	}
	for i := 1; i <= n; i++ {
		xor ^= i
	}
	diff := xor & -xor
	a := 0
	for _, v := range nums {
		if (v & diff) != 0 {
			a ^= v
		}
	}
	for i := 1; i <= n; i++ {
		if (i & diff) != 0 {
			a ^= i
		}
	}
	b := xor ^ a
	return []int{a, b}
}

Swift

class Solution {
    func missingTwo(_ nums: [Int]) -> [Int] {
        let n = nums.count + 2
        var xor = 0

        for num in nums {
            xor ^= num
        }

        for i in 1...n {
            xor ^= i
        }

        let diff = xor & (-xor)

        var a = 0

        for num in nums {
            if (num & diff) != 0 {
                a ^= num
            }
        }

        for i in 1...n {
            if (i & diff) != 0 {
                a ^= i
            }
        }

        let b = xor ^ a
        return [a, b]
    }
}