【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)

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏专知

关关的刷题日记78 – Leetcode 69. Sqrt(x)

关关的刷题日记78 – Leetcode 69. Sqrt(x) 题目 Implement int sqrt(int x). Compute and retur...

36360
来自专栏专知

【 关关的刷题日记49】 Leetcode 434. Number of Segments in a String

关关的刷题日记49 – Leetcode 434. Number of Segments in a String 题目 Count the number of ...

28950
来自专栏机器学习算法与Python学习

长文 | 手把手教你如何使用python进行数据分析(最好将文章代码自己码一遍)

关键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第二 【Python】:排名第三 【算法】:排名第四 原文 http://www.cnbl...

39850
来自专栏专知

关关的刷题日记79 – Leetcode 9 Palindrome Number

关关的刷题日记79 – Leetcode 9 Palindrome Number 题目 Determine whether an integer is a pa...

37080
来自专栏专知

【LeetCode 383】关关的刷题日记41 – Leetcode 383. Ransom Note

关关的刷题日记41 – Leetcode 383. Ransom Note 题目 Given an arbitrary ransom note string a...

36760
来自专栏专知

关关的刷题日记81 – Leetcode 258. Add Digits

关关的刷题日记81 – Leetcode 258. Add Digits 题目 Given a non-negative integer num, repeat...

28070
来自专栏斑斓

迪米特法则与重构

在面向对象设计的世界里,有一个寻常却又常常为人所忽略的原则——“迪米特(Law of Demeter)”法则。这个原则认为,任何一个对象或者方法,它应该只能调用...

12060
来自专栏专知

关关的刷题日记88 – Leetcode 367.Valid Perfect Square

关关的刷题日记88 – Leetcode 367.Valid Perfect Square 题目 Given a positive integer num, w...

31090
来自专栏专知

【LeetCode 136】 关关的刷题日记33 Intersection of Two

关关的刷题日记33 – Leetcode 349. Intersection of Two Arrays 题目 Given two arrays, write ...

29850
来自专栏专知

关关的刷题日记07——Leetcode 26. Remove Duplicates from Sorted Array 方法1

关小刷刷题07 – Leetcode 26. Remove Duplicates from Sorted Array 方法1 题目 Given a sorted...

30140

扫码关注云+社区

领取腾讯云代金券