[LintCode/LeetCode] Single Number III

lanffy 发布于2019-08-14 15:33 / 2938人阅读

摘要：去掉最后一个保留最后一个保留最后一个保留第一个这道题在论坛里参考了和两位仁兄的解法。思想是将中所有的数进行异或运算。不同的两个数异或的结果，一定至少有一位为。最后，将和存入数组，返回。

Problem

Given 2*n + 2 numbers, every numbers occurs twice except two, find them.

Example

Given [1,2,2,3,4,4,5,3] return 1 and 5

Challenge

O(n) time, O(1) extra space.

Note

n & (n-1): 去掉最后一个1；
n & (-n): 保留最后一个1；
n & (~(n-1)): 保留最后一个1；
Integer.highestOneBit(n): 保留第一个1；

这道题在LC论坛里参考了huangjingshu和zhiqing_xiao两位仁兄的解法。思想是：
将A中所有的数进行异或运算。不同的两个数异或的结果diff，一定至少有一位为1。我们只保留diff中的一个1，可以是第一个1，也可以是最后一个1，假设这个1在第i位好了！
然后再次将A中所有的数num和diff相与：
若num & diff的结果为diff，说明这些num的第i位是1：将num与res0异或后存入res0，这样最后异或出来的结果就是两个single number中第i位是1的那个；
同理，若num & diff的结果为0，说明这些num的第i位是0：将num与res1异或后存入res1，这样最后异或出来的结果就是两个single number中第i位是1的那个。
最后，将res1和res0存入res数组，返回。

Solution

public class Solution {
    public List singleNumberIII(int[] A) {
        int diff = 0;
        for (int num: A) {
            diff ^= num;
        }
        //diff &= -diff;
        diff &= ~(diff-1);
        int res0 = 0, res1 = 0;
        for (int num: A) {
            if ((diff & num) == diff) res0 ^= num;
            else res1 ^= num;
        }
        List res = new ArrayList();
        res.add(res0);
        res.add(res1);
        return res;
    }
}

云服务器 GPU云服务器 III single ucos-iii 消息队列 single-spa

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65846.html

[LintCode/LeetCode] Single Number I & II [位运算]

摘要：整个过程相当于，直接在和里去掉既是又是的。所以最后返回的，一定是只出现过一次的，而出现两次的都在里，出现三次的都被消去了。 Single Number I Problem Given 2*n + 1 numbers, every numbers occurs twice except one, find it. Example Given [1,2,2,1,3,4,3], return...

Drinkey 2019-08-14 15:33 评论0 收藏0
[LintCode/LeetCode] Combination Sum I & II

摘要：和唯一的不同是组合中不能存在重复的元素，因此，在递归时将初始位即可。 Combination Sum I Problem Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T...

ThreeWords 2019-08-14 15:23 评论0 收藏0
[LintCode/LeetCode] House Robber III

摘要：解法真的非常巧妙，不过这道题里仍要注意两个细节。中，为时，返回长度为的空数组建立结果数组时，是包括根节点的情况，是不包含根节点的情况。而非按左右子树来进行划分的。 Problem The thief has found himself a new place for his thievery again. There is only one entrance to this area,...

macg0406 2019-08-14 15:34 评论0 收藏0
[LintCode/LeetCode] Contains Duplicate III

Problem Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute dif...

MageekChiu 2019-08-19 10:48 评论0 收藏0
[LintCode/LeetCode] Binary Tree Maximum Path Sum

摘要：调用函数更新路径和的最大值，而函数本身需要递归，返回的是单边路径和。所以函数要返回的是，主函数中返回的却是最上一层根节点处和的较大值，与之前遍历过所有路径的最大值之间的最大值。 Problem Given a binary tree, find the maximum path sum. The path may start and end at any node in the tre...

cnTomato 2019-08-14 15:34 评论0 收藏0