专栏首页小浩算法漫画:位运算系列篇(只出现一次的数字)

漫画:位运算系列篇(只出现一次的数字)

今天是小浩算法“365刷题计划”第62天。仍然分享一道关于位运算颇为简单的题型,同时,从明天开始将会提高难度,大家做好准备。

01 PART

Single Number

这道题,大家先想一想是用什么思路进行求解?

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

PS:建议大家停留个两分钟先想一想...直接拉下去看题解就没什么意思了。

02 PART

题目分析

位运算的题目我们已经讲了好几道了,这道也不例外,也是其中一个非常典型的例子!属于必须掌握的题型。

直接分析,我们要找只出现一次的数字,并且已知了其他的数字都只出现了两次。那么这种一听其实就应该想到需使用位运算来进行求解。最好的,就是在读完题目的瞬间,直接条件反射!(当然,如果你现在第一反应是想到 通过遍历统计,或者其他如使用hashmap 等方式来进行求解,那我觉得你的位运算这块,是有必要加强练习力度的。如果你第一反应,连思路都没有,那我觉得对于整个算法的能力这块,都是比较欠缺的,需要下苦功!)

回到题目,如何使用位运算进行求解呢?对于任意两个数a和b,我们对其使用 “异或”操作,应该有以下性质:

  • 任意一个数和0异或仍然为自己: a⊕0=a
  • 任意一个数和自己异或是0: aa=0
  • 异或操作满足交换律和结合律:

aba=(aa)⊕b=0⊕b=b

可能有人直接都不知道异或是什么,所以还是举个例子,比如5异或3,也就是5⊕3,也就是5^3,是下面这样:

根据分析,得出代码:(c++版本)

//CPP
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for (int num : nums) {
            ans ^= num;
        }
        return ans;
    }
};

(java版本)

//JAVA
class Solution {
    public int singleNumber(int[] nums) {
        int ans = nums[0];
        for (int i = 1; i < nums.length; i++) {
            ans = ans ^ nums[i];
        }
        return ans;
    }
}

(python版本)

//py
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ans = 0
        for i in range(len(nums)):
            ans ^= nums[i]
        return ans

郑重申明(读我的文章必看):

  • 本系列所有教程都不会用到复杂的语言特性,不需要担心没有学过相关语法,使用各语言纯属本人爱好。
  • 作为学术文章,虽然风格可以风趣,但严谨,我是认真的。本文所有代码均在leetcode上进行过测试运行。
  • 算法思想才是最重要的。

03 PART

题目进阶

如果修改上面的题目,除了某个元素只出现一次,其余元素都出现了3次以上,那么该如何求解?

修改一个条件之后,本题的难度大幅度提升!“异或”的方式看起来似乎没办法运用在“其余数出现3次以上”的条件中。那对于这种问题又该如何求解?我这里给出几种思路,大家下去分析一下,明天我会公布这道衍化题型的解决方案:

  • 思路1:使用hashmap,统计每个数字出现的次数,最后返回次数为1的数字。。。然后等待一段时间,接到很遗憾的通知。
  • 思路2:上面的题目,对于相同的两个数,进行异或运算,我们可以进行“抵消”,那是否可以找到一种方式,来让相同的三个数进行相互抵消呢?
  • 思路3:是不是可以通过数学的方式来进行计算?

本文分享自微信公众号 - 小浩算法(xuesuanfa),作者:程序员浩哥

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-03-16

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 漫画:位运算系列篇(缺失数字)

    今天是小浩算法“365刷题计划”第64天。昨天题目的难度可能对很多同学引起了不适,今天将回归一道比较简单的题目,大概耗时2-3分钟即可学习!

    程序员小浩
  • 漫画:神奇的找出只出现一次的数字!

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

    程序员小浩
  • 漫画:美团面试题(整数拆分)

    这两天越来越多的读者私信小浩,说觉得只看题的话,不是很系统,想让我系统的讲一讲各类数据结构。对于这个问题,我统一回复一下,首先后面肯定是有系统的讲解各类数据结构...

    程序员小浩
  • 在python中使用xlrd,xlwt读写excel

    晓歌
  • 学界 | 李飞飞最新论文:结合深度学习和谷歌街景来估算美国人口结构

    AI科技评论按:最近,一篇名为《Using Deep Learning and Google Street View to Estimate the Demog...

    AI科技评论
  • 2048 Game

    You are playing a variation of game 2048. Initially you have a multiset ss of nn...

    AngelNH
  • [转载] MYSQL 5.7中临时文件的使用

    原文:http://blog.itpub.net/7728585/viewspace-2146356/

    二狗不要跑
  • 用Python操控Word

    4月底,我带着自己水的一篇文章,从深圳奔赴美帝西雅图参加了一个制药行业软件用户组2018年年会(PharmaSUG 2018)。听了一些报告,收获不少。在众多报...

    专业余码农
  • 数据加密

    /* 功能:数据加密 日期:2013-05-26 */ #include<stdio.h> #include<stdlib.h> #include<...

    汐楓
  • H2 Database迁移到MySQL【halo】

    大大大黑白格子

扫码关注云+社区

领取腾讯云代金券