文档章节

【leetcode78】Single Number II

fengsehng
 fengsehng
发布于 2016/11/09 09:13
字数 349
阅读 0
收藏 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专栏

我的微信二维码如下,欢迎交流讨论

这里写图片描述

欢迎关注《IT面试题汇总》微信订阅号。每天推送经典面试题和面试心得技巧,都是干货!

微信订阅号二维码如下:

这里写图片描述

© 著作权归作者所有

共有 人打赏支持
fengsehng
粉丝 4
博文 284
码字总数 214494
作品 0
朝阳
程序员
私信 提问
Leetcode 137. Single Number II

文章作者:Tyan 博客:noahsnail.com | CSDN | 简书 1. Description 2. Solution Simple Method O(N) Reference https://leetcode.com/problems/single-number-ii/description/ https://leet......

SnailTyan
2018/07/25
0
0
LeetCode 136 Single Number(只出现一次的数字)

版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50686403 翻译 原文 分析 请参照上一题:LeetCode 260 Single...

nomasp
2016/02/18
0
0
[算法][LeetCode] 数组

[算法][LeetCode]Search a 2D Matrix——二维数组的二分查找 http://www.cnblogs.com/hiddenfox/p/3402797.html 将排序的二维数组看做一维数组来处理。不重构数据的情况下,将二分查找的一维...

素雷
2017/10/19
0
0
LeetCode 137 Single Number II(只出现一次的数字 II)(*)

版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50688103 翻译 原文 分析 这道题我并没有按照题目线性时间和不...

nomasp
2016/02/18
0
0
LeetCode — Single Number II 三进制的使用

题目地址 https://leetcode.com/problems/single-number-ii/ 第一种方法,简单使用字典计数 返回出现次数为1的数即可 第二种方法,求和法 使用set将数组中的数字过滤为只出现一次,则set中的...

阿豪boy
2018/06/06
0
0

没有更多内容

加载失败,请刷新页面

加载更多

搜索引擎(Solr-索引详解)

时间字段类型特别说明 Solr中提供的时间字段类型( DatePointField, DateRangeField,废除的TrieDateField )是以时间毫秒数来存储时间的。 要求字段值以ISO-8601标准格式来表示时间:YYYY-MM...

这很耳东先生
24分钟前
0
0
Java成神之路

1、基础篇 01、面向对象 → 什么是面向对象 面向对象、面向过程 面向对象的三大基本特征和五大基本原则 → 平台无关性 Java 如何实现的平台无关 JVM 还支持哪些语言(Kotlin、Groovy、JRuby...

asdf08442a
54分钟前
2
0
dubbo源码分析-服务导出

简介 dubbo框架spring Schema扩展机制与Spring集成,在spring初始化时候加载dubbo的配置类。 dubbo服务导出的入口类是ServiceBean的onApplicationEvent方法 ServiceBean的继承关系如下 publ...

王桥修道院副院长
今天
0
0
QQ音乐的动效歌词是如何实践的?

本文由云+社区发表 作者:QQ音乐技术团队 一、 背景 1. 现状 歌词浏览已经成为音乐app的标配,展示和动画效果也基本上大同小异,主要是单行的逐字染色的卡拉OK效果和多行的滚动效果。当然,我...

腾讯云加社区
今天
4
0
idea里配置springboot项目打热部署

首先添加依赖 <dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-devtools</artifactId> <optional>true</optional></dependency> 然后添......

shatian
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部