Leetcode 137.Single Number II

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

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

题意:136的followup,这次数组中出现的都是3次,求只出现一次的那个数。

思路:
这道题自己没想到不用额外空间的方法,看discuss有一种方法比较容易懂。
即这个数组每个数投射到一个int类型32位bit上,统计每一个bit位上的总个数。如果某个bit位上和数是3的倍数,那么那个只出现一次的数肯定不会投射到这个bit位。最后把每个位上的和对3取余,然后按位算出所求数字。

public int singleNumber(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }

    int res = 0;
    for (int i = 0; i < 32; i++) {
        int cnt = 0;
        for (int num : nums) {
            num = (num >> i) & 1;
            cnt += num;
        }
        cnt %= 3;
        res += cnt << i;
    }

    return res;
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容