admin管理员组

文章数量:1576836

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

 

【位运算】先把所有的n个数异或得到sum，然后再把结果和数组中的所有数异或，这样就只剩下最后两个数异或的结果了，接下来就是如何将两个数分开，由于他们不同，所以至少有一位不相同，那么这一位异或的结果必然是1，所以我们可以通过lowbit操作找到最后一个1。

lowbit(x) = x & ( -x)，举个🌰

10010 -> 10010 & 01110 = 00010

接下来根据&low的值为0或者为1，可以把所有n和所有arr中的数分开，然后分别异或就得到两个数了。

class Solution {
    public int[] missingTwo(int[] nums) {
        // 位运算
        int n = nums.length + 2;
        int sum = 1;
        for (var i = 2; i <= n; i++) sum ^= i;
        // 1011
        // 1101   0110  
        for (var x: nums) sum ^= x;
        // 1010
        // 0110 0010
        int low = sum & (-sum);
        int left = 0, right = 0;
        for (var i = 1; i <= n; i++) {
            if ((i & low) == low) left ^= i;
            else right ^= i;
        }
        for (var x: nums) {
            if ((x & low) == low) left ^= x;
            else right ^= x;
        }
        return new int[] {left, right};
    }
}

 

 

本文标签： 面试题两个数字LeetCode

版权声明：本文标题：LeetCode 面试题 17.19. 消失的两个数字 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://www.elefans.com/xitong/1727803951a1130864.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。