【Leetcode】137.只出现一次的数字 II

栏目: 编程工具 · 发布时间: 4年前

内容简介:给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现了三次。找出那个只出现了一次的元素。说明:你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

题目

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现了三次。找出那个只出现了一次的元素。

说明:

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

示例 1:

输入: [2,2,3,2]
输出: 3

示例 2:

输入: [0,1,0,1,0,1,99]
输出: 99

题解

根据上一道题目的经验,我们很明确的知道不能用数数字的办法去解。考虑位运算的办法,找相关的性质。

这个题其实就是求,在其他数都出现k次的数组中有一个数只出现一次,求出这个数。

而上面那个k次的是有通用解法的。

使用一个32维的数组,用这个32维的数组存储:

[第31位1的总数, 第30位1的个数,…, 第1位1的个数]

  • 假如第0位1的个数是k的倍数,那么要求的这个数在该位一定是0;
  • 若不是k的倍数,那么要求的这个数在该位一定是1。

    因为假如说数组中的某些数在该位置是1,那么因为这个数要么出现k次,那么出现1次。

这样我们就可以找出只出现一次那个数的二进制表示形式。二进制如何转化为10进制呢?

假如,按照上面的规则,最招找到的二进制为:

A = [0, 0, 0, 0, 0, …, 1]

因为异或操作是:相同为0,不同为1。

那么久可以依次用 1, 2, 4, 8… 和依次每一位异或,即可得到最终答案。

第二部分可能不好理解,可以手动模拟下。

class Solution {
    public int singleNumber(int[] nums) {
        // 有多少个相同的数字
        int N = 3;
        // [高位1的个数,...,低位1的个数]
        int[] bitNum = new int[32];
        
        for (int i = 0; i < nums.length; i++) {
            int compare = 1;
            int num = nums[i];
            for (int j = bitNum.length - 1; j >= 0; j--) {
                if ((compare&num) != 0) {
                    bitNum[j]++;
                }
                compare = compare << 1;
            }
        }
        
        int compare = 1;
        int res = 0;
        for(int i = bitNum.length - 1; i >= 0; i--) {
            if(bitNum[i] % N != 0) {
                res = res ^ compare;
            }
        }
        return res;
   }
}

热门阅读


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

大思维:集体智慧如何改变我们的世界

大思维:集体智慧如何改变我们的世界

杰夫·摩根 / 郭莉玲、尹玮琦、徐强 / 中信出版集团股份有限公司 / 2018-8-1 / CNY 65.00

智能时代,我们如何与机器互联,利用技术来让我们变得更聪明?为什么智能技术不会自动导致智能结果呢?线上线下群体如何协作?社会、政府或管理系统如何解决复杂的问题?本书从哲学、计算机科学和生物学等领域收集见解,揭示了如何引导组织和社会充分利用人脑和数字技术进行大规模思考,从而提高整个集体的智力水平,以解决我们时代的巨大挑战。是英国社会创新之父的洞见之作,解析企业、群体、社会如何明智决策、协作进化。一起来看看 《大思维:集体智慧如何改变我们的世界》 这本书的介绍吧!

JS 压缩/解压工具
JS 压缩/解压工具

在线压缩/解压 JS 代码

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具