【leetcode78】Single Number II

我不是女神ヾ 2022-04-11 06:31 110阅读 0赞

# 题目描述： #

## 给定一个数组，里面除了一个数字，其他的都出现三次。求出这个数字 ##

# 原文描述： #

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?

Subscribe to see which companies asked this question

# 思路： #

*  设置一个32位的数组，然然后对数组，Array【i】代表i位的1个数，统计整个数组nums【】的数字，对于每个Array【i】做mod3的运算
 *  遍历nums【】数组时候，是左移&1取出，加到Array【i】上面，然后mod3
 *  最后右移加到result上面

# 代码： #

// Single Number II
    // 方法1，时间复杂度O(n)，空间复杂度O(1)
    public class Solution {
        public int singleNumber(int[] nums) {
            final int W = Integer.SIZE; // 一个整数的bit数，即整数字长
            int[] count = new int[W];  // count[i]表示在在i位出现的1的次数
            for (int i = 0; i < nums.length; i++) {
                for (int j = 0; j < W; j++) {
                    count[j] += (nums[i] >>> j) & 1;
                    count[j] %= 3;
                }
            }
            int result = 0;
            for (int i = 0; i < W; i++) {
                result += (count[i] << i);
            }
            return result;
        }
    };

# 更多的leetcode的经典算法，查看我的leetcode专栏，链接如下： #

[leetcode专栏][leetcode]

# #

[leetcode]: http://blog.csdn.net/column/details/fengsheng.html

发表评论取消回复

表情：

评论列表（有 0 条评论，110人围观）

还没有评论，来说两句吧...

相关阅读

相关【leetcode78】Single Number II

题目描述：给定一个数组，里面除了一个数字，其他的都出现三次。求出这个数字原文描述： Given an array of integers, every e

蔚落/ 2022年09月24日 12:28/ 0 赞/ 88 阅读

相关 137 Single Number II

原题目提示可以使用位运算，但是不会用 public class Solution { public int singleNumber(int[] nu

待我称王封你为后i/ 2022年08月04日 09:18/ 0 赞/ 86 阅读

相关 LeetCode－136. Single Number/137. Single Number II/260. Single Number III

136. Single Numbe Problem： > Given an array of integers, every element appears twice

待我称王封你为后i/ 2022年07月26日 04:12/ 0 赞/ 121 阅读

相关 leetcode 137. Single Number II -->hashmap

137. Single Number II Question Editorial Solution [My Submissions][] Total Accep

落日映苍穹つ/ 2022年07月19日 01:24/ 0 赞/ 82 阅读

相关 LeetCode137—Single Number II

原题 [原题链接][Link 1] > Given an array of integers, every element appears three times ex

灰太狼/ 2022年07月18日 09:05/ 0 赞/ 108 阅读

相关 [Leetcode]Single Number

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

淩亂°似流年/ 2022年06月09日 03:06/ 0 赞/ 126 阅读

相关 leetcode 137. Single Number II

Given an array of integers, every element appears three times except for one, which appe

灰太狼/ 2022年06月08日 05:59/ 0 赞/ 100 阅读

相关 [Leetcode][python]Single Number/Single Number II

Single Number 题目大意一个数组中除了一个数字出现过一次外，其余的数字都出现了两次，找出那个只出现一次的数字。注意点：算法时间杂度要求为O

小鱼儿/ 2022年06月04日 23:43/ 0 赞/ 109 阅读

相关 Leetcode|136. Single Number

【问题描述】 Given a non-empty array of integers, every element appears twice except for one.

迈不过友情╰/ 2022年05月25日 12:48/ 0 赞/ 114 阅读

相关【leetcode78】Single Number II

题目描述：给定一个数组，里面除了一个数字，其他的都出现三次。求出这个数字原文描述： Given an array of integers, every e

我不是女神ヾ/ 2022年04月11日 06:31/ 0 赞/ 111 阅读