Leetcode 137 Single Number II

triplebee

发布于 2018-01-12 14:52:46

5210

发布于 2018-01-12 14:52:46

文章被收录于专栏：计算机视觉与深度学习基础计算机视觉与深度学习基础

Given an array of integers, every element appears three times except for one. Find that single one.

Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

找出只出现一次的数字。

统计每一位出现的次数，对3取余可以得到每一位是否为1

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for(int i = 0 ; i < 32; i++)
        {
            int cnt = 0 ;
            for(int j  = 0; j < nums.size() ;j++) cnt += ((1 << i) & nums[j])>>i;
            res |= cnt % 3 << i;
        }
        return res;
    }
};

在discuss中看到一种awesome的做法，不是很能理解，知道的朋友可以在评论中告诉我！

public int singleNumber(int[] A) {
    int ones = 0, twos = 0;
    for(int i = 0; i < A.length; i++){
        ones = (ones ^ A[i]) & ~twos;
        twos = (twos ^ A[i]) & ~ones;
    }
    return ones;
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2016-11-16 ，如有侵权请联系 cloudcommunity@tencent.com 删除

algorithm