题解 | #合并两个有序的数组#

数组中只出现一次的两个数字

http://www.nowcoder.com/practice/389fc1c3d3be4479a154f63f495abff8

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param array int整型vector
     * @return int整型vector
     */
    int xorRes(vector<int>& array) { // 寻找数组中只出现一次的数字(一轮xor只能找出一个)
        int sum = array[0];
        for (int i = 1; i < array.size(); i++) {
            sum = array[i] ^ sum;
        }
        return sum;
    }
    vector<int> FindNumsAppearOnce(vector<int>& array) {
        // write code here
        int sum = xorRes(array);
        int cnt = 0; // 计算二进制中两个只出现一次的数字的差异位置
                    // 如4(100)和6(110),则在第二个二进制位有差异(xor异为1同为0)
        while (sum % 2 == 0) {
            sum /= 2;
            cnt++;
        }
        vector<int> arr1;
        vector<int> arr2;
        vector<int> res;
        for (int i = 0; i < array.size(); i++) {
            if ((array[i] >> cnt)%2 == 0) // 右移至差异位,则差异位为1的元素为一类,为0的元素为另一类,
                                        //两类分别调用xorRes即得到两个只出现一次的数字
                arr1.push_back(array[i]);
            else
                arr2.push_back(array[i]);
        }
        int a = xorRes(arr1), b = xorRes(arr2);
        if(a > b)
            swap(a, b);
        res.push_back(a);
        res.push_back(b);
        return res;
    }
};
全部评论

相关推荐

07-03 11:02
中山大学 C++
字节刚oc,但距离九月秋招很近了有两段互联网实习,非腾讯字节。不敢赌转正,现在在纠结去还是不去如果实习俩月离职会有什么后果吗
阿城我会做到的:不去后悔一辈子,能否转正取决于ld的态度,只要他不卡,答辩就是走流程,个人觉得可以冲一把
投递字节跳动等公司10个岗位
点赞 评论 收藏
分享
认真搞学习:28小登的建议,投算法岗不要写什么物理竞赛,互联网+,多写点项目,用什么算法做了什么。还有本科算法是不可能的开发你这个也没有项目啊
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务