Loading [MathJax]/jax/input/TeX/config.js
前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >只出现一次的数字

只出现一次的数字

原创
作者头像
_kyle
修改于 2023-09-24 06:07:57
修改于 2023-09-24 06:07:57
93400
代码可运行
举报
文章被收录于专栏:kyle的专栏kyle的专栏
运行总次数:0
代码可运行

题目

难度级别:简单

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

说明:

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

示例 1:

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

示例 2:

输入: [4,1,2,1,2] 输出: 4

解题思路

法一

倒叙遍历相等则删除,时间复杂度为O(n^2),不满足线性时间复杂度O(n),而且这个方法也太慢了。。。执行用时如下图。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
const singleNumber = function(nums) {
    for(let i = nums.length; i >= 0; i--) {
        for(let j = i - 1; j >= 0; j--) {
            if (nums[i] === nums[j]) {
                nums.splice(i, 1) && nums.splice(j, 1) 
                continue;
            }
        }
    }

    return nums[0]
};

法二:位运算

上图方法太慢,考虑到线性时间复杂度和常数空间复杂度,使用位运算,因为它满足交换律和结合律

即: a | a = 0,a | 1 = a , a | 1 | a = a | a | 1

再看一下执行时间,快了好多。。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
const singleNumber = function(nums) {
    for(let i = 1; i < nums.length; i++) 
        nums[0] ^= nums[i]
        
    return nums[0]
};

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/single-number

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
leecode刷题(5)-- 只出现一次的数字
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
希希里之海
2019/01/03
5170
​LeetCode刷题实战136:只出现一次的数字
https://leetcode-cn.com/problems/single-number/
程序员小猿
2021/01/19
2920
LeetCode 进阶之路 - 136.只出现一次的数字
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。 说明: 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗? 示例 1: 输入: [2,2,1] 输出: 1 示例 2: 输入: [4,1,2,1,2] 输出: 4 我的脑子只想出暴力方法来解,看了题解后发现可以用位运算,真是巧妙。 /** * 136. 只出现一次的数字 * @Author: lixj * @Date: 2020/9/21 10:19 */ public
Li_XiaoJin
2022/06/10
1780
LeetCode 热题 100 - 只出现一次的数字
 ,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
陈明勇
2025/01/31
16112
画解算法:136. 只出现一次的数字
https://leetcode-cn.com/problems/single-number/
灵魂画师牧码
2019/06/27
3630
画解算法:136. 只出现一次的数字
最常见面试算法之只出现1次的数字
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
阿宝哥
2020/02/14
4150
【每日leetcode】8.只出现一次的数字
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
一条coding
2021/08/12
3100
【每日leetcode】8.只出现一次的数字
LeetCode-136-只出现一次的数字
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
benym
2022/07/14
1730
【leetcode系列】136. 只出现一次的数字
https://leetcode.com/problems/single-number/description/
lucifer210
2019/08/16
3900
【Leetcode】136.只出现一次的数字
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
Leetcode名企之路
2019/07/09
4990
Leetcode No.136 只出现一次的数字
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
week
2021/05/06
2340
LeetCode-136. 只出现一次的数字(java)
       这题相对其他简答题还要简答,所以题目难度我给了一星,分析题意可得要求找出只出现一次的那个数字,那么通常能想到的实现方式有哪些呢?(除了双层循环嵌套暴力法啊)
bug菌
2023/05/27
2700
LeetCode-136. 只出现一次的数字(java)
LeetCode 136. 只出现一次的数字(异或^)
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
Michael阿明
2021/02/20
2770
LeetCode 136. 只出现一次的数字(异或^)
位运算问题-LeetCode 136、137、260(只出现一次的数,异或运算)
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。 说明: 你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗?
算法工程师之路
2019/11/04
6330
LeetCode84|只出现一次的数字
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
码农王同学
2020/10/14
4450
LeetCode 136:只出现一次的数字 Single Number
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
爱写bug
2019/10/12
4570
leetocode刷题(66)—— 136. 只出现一次的数字
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
老马的编程之旅
2022/06/22
1610
日拱算法:只出现一次的数字
持续创作,加速成长!这是我参与「掘金日新计划 · 6 月更文挑战」的第26天,点击查看活动详情
掘金安东尼
2022/09/19
1990
日拱算法:只出现一次的数字
☆打卡算法☆LeetCode 136. 只出现一次的数字 算法解析
“给定一个数组,除了某个元素只出现一次,其他元素都出现两次,找出那个只出现一次的元素。”
恬静的小魔龙
2022/08/07
2030
☆打卡算法☆LeetCode 136. 只出现一次的数字  算法解析
LeetCode通关:求次数有妙招,位运算三连
大家好,我是刷题困难户老三,这一节我们来刷几道很有意思的求次数问题,它们都有同一类非常巧妙的解法。
三分恶
2021/08/06
3830
推荐阅读
相关推荐
leecode刷题(5)-- 只出现一次的数字
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验