LeetCode 136. 只出现一次的数字【c++/java详细题解】_169. 多数元素c++_林小鹿@的博客-程序员秘密

1、题目

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

说明：

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

示例 1:

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

示例 2:

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

2、思路

(位运算) $O (n)$

异或运算有以下三个性质:

1、0^0 = 0 ，0^1 = 1，0异或任何数＝任何数
2、1^0 = 1 ，1^1 = 0，1异或任何数 = 任何数取反
3、任何数异或自己＝把自己置0，即 a^a=0

因此这道题可以用位运算来做，过程如下：

1、两个相同的元素经过异或之后会变为0。
2、将数组所有元素异或在一起即可得到出现 1 次的元素值。

时间复杂度分析： $O (n)$ ，其中 $n$ 是数组长度。

3、c++代码

class Solution {
    
public:
    int singleNumber(vector<int>& nums) {
    
        int res = 0;
        for(int i = 0; i < nums.size(); i++) res ^= nums[i];
        return res;
    }
};

4、java代码

class Solution {
    
    public int singleNumber(int[] nums) {
    
        int res = 0;
        for(int i = 0;i < nums.length;i ++) res ^= nums[i];
        return res;
    }
}

原题链接：136. 只出现一次的数字

在这里插入图片描述

本文链接：https://blog.csdn.net/weixin_45629285/article/details/119598167

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

python 列表排序方法sort、sorted技巧篇_张博208的博客-程序员秘密

Python list内置sort()方法用来排序，也可以用python内置的全局sorted()方法来对可迭代的序列排序生成新的序列。1）排序基础简单的升序排序是非常容易的。只需要调用sorted()方法。它返回一个新的list，新的list的元素基于小于运算符(__lt__)来排序。&gt;&gt;&gt; sorted([5, 2, 3, 1, 4])[1, 2, 3, 4, 5]你也可以...

word2vec中CBOW和Skip-Gram训练模型的原理_dxlcnm的博客-程序员秘密

转载于CBOW模型和Skip-Gram模型前言word2vec如何将corpus（语料库）的one-hot向量（模型的输入）转换成低维词向量（模型的中间产物，更具体来说是输入权重矩阵），真真切切感受到向量的变化，暂不涉及加速算法。CBOW模型根据中心词W(t)周围的词来预测中心词：Skip-gram模型则根据中心词W(t)来预测周围词：CBOW模型的理解假设我们现在的Corpus是这一个简单的只有...

Win10客户端 ssh 远程连接 win server 2008 R2服务器_remote ssh 2008_mingyong.g的博客-程序员秘密

Win10客户端 ssh 远程连接 win server 2008 R2服务器写在前面如题，本文介绍的是在Win10客户端和 win server 2008 R2服务器之间建立 ssh 连接。网上很多关于ssh介绍的教程文章，但是都没有讲清楚基本环境，导致读者看完后找不到头脑。再多说一句，服务器是阿里云的服务器，操作系统是Windows Server 2008 R2 企业版64位中文版。开始配置win10 客户端win 10 系统已经内置了open SSH 客户端和服务端，因此在win 10

C语言之数组的使用,C语言之数组的使用_小麦的天空的博客-程序员秘密

要想把数据放入内存，必须先要分配内存空间。放入4个整数，就得分配4个int类型的内存空间：定义数组 inta[length];数组名叫a。这样的一组数据的集合称为数组(Array)，它所包含的每一个数据叫做数组元素(Element)，所包含的数据的个数称为数组长度(Length)，例如inta[4];就定义了一个长度为4的整型数组，名字是a。数组中的每个元素都有一个序号，这个序号从0开始，而不是...

CSS布局——链接文字水平居中垂直居中_超链接文字怎么居中_qq591840685的博客-程序员秘密

布局（一）

一个tomcat下有多个应用时多个Context启动冲突的问题解决_tomcat多个context_quanzhoushi的博客-程序员秘密

关于一个tomcat下有多个应用的冲突问题