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

Categories:

题目描述
思路分析
1. 解法一：按位异或拆分（推荐）
相似题目

题目描述

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

思路分析

解法一：按位异或拆分（推荐）

核心思路：

设缺失的两个数为 a 和 b，对 1..n 与数组所有元素异或，可得 xor = a ^ b。

取 xor 的最低位 1，把所有数按该位分成两组，分别异或即可得到 a 和 b。

最后按需调整输出顺序。

复杂度分析：

时间复杂度：O(n)，其中 n 为完整数组长度。

空间复杂度：O(1)，仅使用常数额外空间。

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

        for (int i = 1; i <= n; i++) {
            xor ^= i;
        }

        for (int num : nums) {
            xor ^= num;
        }

        int lowbit = xor & -xor;
        int a = 0;
        int b = 0;

        for (int i = 1; i <= n; i++) {
            if ((i & lowbit) == 0) {
                a ^= i;
            } else {
                b ^= i;
            }
        }

        for (int num : nums) {
            if ((num & lowbit) == 0) {
                a ^= num;
            } else {
                b ^= num;
            }
        }

        if (a > b) {
            int tmp = a;
            a = b;
            b = tmp;
        }

        return new int[]{a, b};
    }
}

func missingTwo(nums []int) []int {
	n := len(nums) + 2
	xor := 0

	for i := 1; i <= n; i++ {
		xor ^= i
	}

	for _, num := range nums {
		xor ^= num
	}

	lowbit := xor & -xor
	a, b := 0, 0

	for i := 1; i <= n; i++ {
		if i&lowbit == 0 {
			a ^= i
		} else {
			b ^= i
		}
	}

	for _, num := range nums {
		if num&lowbit == 0 {
			a ^= num
		} else {
			b ^= num
		}
	}

	if a > b {
		a, b = b, a
	}

	return []int{a, b}
}

相似题目

题目	难度	考察点
268. 丢失的数字	简单	位运算
260. 只出现一次的数字 III	中等	位运算
136. 只出现一次的数字	简单	位运算
645. 错误的集合	简单	位运算
448. 找到所有数组中消失的数字	简单	哈希/原地标记

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/87492956