当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.137.Single Number II 数组中只出现一次的数2

LeetCode.137.Single Number II 数组中只出现一次的数2

题目描述

137 Single Number II
https://leetcode-cn.com/problems/single-number-ii/

Given a non-empty 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?

Example 1:

Input: [2,2,3,2]
Output: 3

Example 2:

Input: [0,1,0,1,0,1,99]
Output: 99

解题过程

位操作,统计所有元素在每位上的和对3求余,由于其他数一定出现3次所以结果就是唯一数在此位的值。此方法还可以推广到所有元素出现了p次只有一个出现了k次的情况。

时间复杂度 O(n),空间复杂度 O(1)

private static class SolutionV2020 {
    public int singleNumber(int[] nums) {
        int res = 0;
        // 所有元素在每位上的和对3求余,结果就是唯一数在此位的值
        for (int i = 0; i < 32; i++) {
            int bitSum = 0;
            for(int j = 0; j < nums.length; j++) {
                bitSum += nums[j] & 1;
                nums[j] >>= 1;
            }
            res |= (bitSum % 3) << i;
        }
        return res;
    }
}

GitHub代码

leetcode-java/problems/_137_SingleNumber2.java
https://github.com/masikkk/leetcode-java/blob/master/problems/_137_SingleNumber2.java


上一篇 LeetCode.448.Find All Numbers Disappeared in an Array 数组中消失的数

下一篇 LeetCode.268.Missing Number 连续数组中缺失的数

阅读
评论
256
阅读预计1分钟
创建日期 2020-02-12
修改日期 2020-02-12
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论