【力扣】136. 只出现一次的数字

简介: 【力扣】136. 只出现一次的数字

题目描述

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

你必须设计并实现线性时间复杂度的算法来解决此问题,且该算法只使用常量额外空间。

示例 1 :

输入:nums = [2,2,1]

输出:1

示例 2 :

输入:nums = [4,1,2,1,2]

输出:4

示例 3 :

输入:nums = [1]

输出:1


提示:

  • 1 <= nums.length <= 3 * 104
  • -3 * 104 <= nums[i] <= 3 * 104
  • 除了某个元素只出现一次以外,其余每个元素均出现两次。


解题方案

暴力破解

不考虑时间复杂度和空间复杂度限制

  • C
int singleNumber(int* nums, int numsSize) {

    for(int i = 0; i < numsSize; i++)
    {
        for(int j = i + 1; j < numsSize; j++)
        {
            if(nums[i] == nums[j])
            {
                nums[i] = 0;
                nums[j] = 0;
            }
        }

        if(nums[i] != 0)
        {
            return nums[i];
        }
    }

    return 0;
}

位运算-异或运算法:

根据异或运算的性质,数组中的全部元素的异或运算结果即为数组中只出现一次的数字。


异或性质

(1)交换律: A ^ B = B ^ A

(2)结合律: ( A ^ B ) ^ C = A ^ ( B ^ C )

(3)自反性: A ^ B ^ B = A (由结合律可推: A ^ B ^ B = A ^ ( B ^ B ) = A ^ 0 = A)


  • C
int singleNumber(int* nums, int numsSize) {

    int temp = 0;

    for(int i = 0; i < numsSize; i++)
    {
        temp ^= nums[i];
    }

    return temp;
}


复杂度分析

  • 时间复杂度:O(n),其中 n 是数组长度。
  • 空间复杂度:O(1)。


相关文章
|
BI
解决File.delete()删除不掉文件
首先注意两点: 此文件被使用的时候无法删除(比如网络输出没关闭流) 判断此文件是否存在再做删除(exists) 删除文件夹之前先删除文件夹下的所有文件(递归解决) 判断是否删除成功会有返回值,文件名错了的话,删除文件不会报错。
2452 0
|
JSON 安全 API
淘宝 API 接口:解锁商品详情的强大工具
淘宝API接口在电商领域扮演着关键角色,为商家和开发者提供强大的数据支持和服务能力。它不仅帮助商家获取商品信息、管理订单和物流,还支持数据分析、价格调整等功能,助力商家在竞争激烈的市场中取得成功。此外,通过注册认证、搭建开发环境等步骤,开发者可快速上手并利用丰富的技术文档和社区支持进行高效开发。
|
6月前
|
数据采集 人工智能 缓存
深挖“全栈智算”之力 中兴通讯开启AI普惠新纪元
深挖“全栈智算”之力 中兴通讯开启AI普惠新纪元
194 1
|
编译器 vr&ar 图形学
从零开始的unity3d入门教程(五)---- 基于Vuforia的AR项目
这是一篇Unity3D结合Vuforia实现增强现实(AR)项目的入门教程,涵盖了环境配置、Vuforia账户注册、Target数据集创建、Unity项目设置、AR程序配置、Android环境配置以及最终在手机上测试运行的全过程。
从零开始的unity3d入门教程(五)---- 基于Vuforia的AR项目
|
消息中间件 Ubuntu Java
Kafka安装部署
Kafka安装部署
|
运维 网络协议 Linux
2023年河南省中等职业教育技能大赛网络建设与运维项目比赛试题(一)
2023年河南省中等职业教育技能大赛网络建设与运维项目比赛试题(一)
|
存储 算法 Java
【经典算法】LeetCode 136:只出现一次的数字(Java/C/Python3实现含注释说明,Easy)
【经典算法】LeetCode 136:只出现一次的数字(Java/C/Python3实现含注释说明,Easy)
144 1
|
Kubernetes Cloud Native Linux
容器引擎Docker与Podman解析
最近技术群里有朋友问我,不是说K8S要弃用Docker了吗?还要不要继续学习这块内容?是不是得改行卖白菜了?
547 0
容器引擎Docker与Podman解析
|
程序员
开发中遇到问题如何更好地提问
开发中遇到问题如何更好地提问
116 0
|
测试技术 C语言
C语言题解 | 移除元素(多种解法)
这是力扣上的一道简单题,需求是 移除数组中的指定元素,并且要求 空间复杂度为O(1) ,即原地移除,我们可以用顺序表中的任意位置删除的思想解决这个题,符合题目要求,当然还有其他解法。
50287 1
C语言题解 | 移除元素(多种解法)