专栏首页专知【LeetCode 136】 关关的刷题日记32 Single Number

【LeetCode 136】 关关的刷题日记32 Single Number

关关的刷题日记32 – Leetcode 136. Single Number

题目

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

Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

题目的意思是有一个数组,每个元素出现两次,只有一个元素出现了一次,让找出该元素。

思路

思路:没细看题目,随手写了个map。

class Solution {public:
    int singleNumber(vector<int>& nums) {
        map<int,int>m;
        for(int x:nums)
        {
            m[x]++;
        }
        for(int x:nums)
        {
            if(m[x]==1)
                return x;
        }
        return 0;
    }};

方法2:发现题目要求O(n)时间复杂度,而且不需要额外空间。Map开辟了额外空间,不满足要求。采用异或的思路,遍历一边该数组即可。 aa=0 ab=ba a0=a

class Solution {public:
    int singleNumber(vector<int>& nums) {
        int re=0;
        for(int x:nums)
        {
            re^=x;
        }
        return re;
    }};

人生易老,唯有陪伴最长情,加油!

以上就是关关关于这道题的总结经验,希望大家能够理解,有什么问题可以在我们的专知公众号平台上交流或者加我们的QQ专知-人工智能交流群 426491390,也可以加入专知——Leetcode刷题交流群(请先加微信小助手weixinhao: Rancho_Fang,注明Leetcode刷题)。

本文分享自微信公众号 - 专知(Quan_Zhuanzhi),作者:关关

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

原始发表时间:2017-11-11

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 关小刷刷题02——Leetcode 169. Majority Element 方法2和3

    题目 169. Majority Element Given an array of size n, find the majority element. Th...

    WZEARW
  • 【专知-关关的刷题日记17】Leetcode 268. Missing Number

    题目 Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find...

    WZEARW
  • 关关的刷题日记05 —— Leetcode 219. Contains Duplicate II

    关小刷刷题06 – Leetcode 219. Contains Duplicate II 题目 Given an array of integers and ...

    WZEARW
  • 3339: Rmq Problem

    Description image.png Input image.png Output image.png Sample Input 7 5 ...

    attack
  • leetcode之错误的集合

    这里遍历一次数组,求出总和,并计算每个元素的count,同时找出重复的元素,之后根据自然数求和公式与现有总和的差值及重复的元素计算得出缺失的元素。

    codecraft
  • leetcode之错误的集合

    这里遍历一次数组,求出总和,并计算每个元素的count,同时找出重复的元素,之后根据自然数求和公式与现有总和的差值及重复的元素计算得出缺失的元素。

    codecraft
  • BZOJ3529: [Sdoi2014]数表(莫比乌斯反演 树状数组)

    \[\sum_{i = 1}^n \sum_{j = 1}^m \sigma(gcd(i, j))\]

    attack
  • 洛谷P2447 [SDOI2010]外星千足虫(异或方程组)

    找最优解可以考虑高斯消元的过程,因为异或的特殊性质,每次向下找的时候找到第一个1然后交换就行,这样显然是最优的

    attack
  • 西南民族大学程序竞赛

    No matter what activities you join,whether you want or not, you could gain unexp...

    AngelNH
  • Educational Codeforces Round 65 (Rated for Div. 2) A-D

    rank是能够通知到的人的个数,比较当前这两个人谁能通知到的人较少,然后把能通知到的人较少的那个人的指向pre[a]指向b(假设a能通知到的人较少),这样是为了...

    用户2965768

扫码关注云+社区

领取腾讯云代金券