前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
社区首页 >专栏 >只出现一次的数字

只出现一次的数字

原创
作者头像
_kyle
修改于 2023-09-24 06:07:57
修改于 2023-09-24 06:07:57
78200
代码可运行
举报
文章被收录于专栏: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 删除。

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
画解算法:136. 只出现一次的数字
https://leetcode-cn.com/problems/single-number/
灵魂画师牧码
2019/06/27
3540
画解算法:136. 只出现一次的数字
136. 只出现一次的数字
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
张伦聪zhangluncong
2022/10/26
3680
Leetcode No.136 只出现一次的数字
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
week
2021/05/06
2250
最常见面试算法之只出现1次的数字
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
阿宝哥
2020/02/14
3840
LeetCode-136. 只出现一次的数字(java)
       这题相对其他简答题还要简答,所以题目难度我给了一星,分析题意可得要求找出只出现一次的那个数字,那么通常能想到的实现方式有哪些呢?(除了双层循环嵌套暴力法啊)
bug菌
2023/05/27
2600
LeetCode-136. 只出现一次的数字(java)
【leetcode系列】136. 只出现一次的数字
https://leetcode.com/problems/single-number/description/
lucifer210
2019/08/16
3770
leecode刷题(5)-- 只出现一次的数字
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
希希里之海
2019/01/03
5040
​LeetCode刷题实战136:只出现一次的数字
https://leetcode-cn.com/problems/single-number/
程序员小猿
2021/01/19
2820
【每日leetcode】8.只出现一次的数字
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
一条coding
2021/08/12
3020
【每日leetcode】8.只出现一次的数字
LeetCode-136-只出现一次的数字
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
benym
2022/07/14
1570
LeetCode 136. 只出现一次的数字(异或^)
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
Michael阿明
2021/02/20
2700
LeetCode 136. 只出现一次的数字(异或^)
LeetCode,只出现一次的数字
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
微客鸟窝
2021/08/18
5900
LeetCode,只出现一次的数字
【Leetcode】136.只出现一次的数字
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
Leetcode名企之路
2019/07/09
4910
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
1650
☆打卡算法☆LeetCode 136. 只出现一次的数字 算法解析
“给定一个数组,除了某个元素只出现一次,其他元素都出现两次,找出那个只出现一次的元素。”
恬静的小魔龙
2022/08/07
1960
☆打卡算法☆LeetCode 136. 只出现一次的数字  算法解析
LeetCode | 只出现一次的数字
题目 136. 只出现一次的数字 - 力扣(LeetCode) 给你一个 非空 整数数组 nums ,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。 你必须设计并实现线性时间复杂度的算法来解决此问题,且该算法只使用常量额外空间。 示例 1 :
yiyun
2023/04/04
5510
LeetCode | 只出现一次的数字
java位运算
从现代计算机中所有的数据二进制的形式存储在设备中。即 0、1 两种状态,计算机对二进制数据进行的运算(+、-、*、/)都是叫位运算,即将符号位共同参与运算的运算。
周杰伦本人
2022/10/25
7740
java位运算
LeetCode84|只出现一次的数字
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
码农王同学
2020/10/14
4320
LeetCode 136:只出现一次的数字 Single Number
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
爱写bug
2019/10/12
4420
找只出现一次的数字
  给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
Qt君
2020/08/05
6610
相关推荐
画解算法:136. 只出现一次的数字
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
查看详情【社区公告】 技术创作特训营有奖征文
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验