136. Single Number 找数组只出现一次的数字

2024-06-22 06:38

本文主要是介绍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?

思路:这道题不像之前的540. Single Element in a Sorted Array是有序序列,更复杂.
(看讨论的)用异或(XOR,或记为⊕)
以下结论很吊很有用:

0A = A //A为任意数
AA = 0
即,任意数与0相与都等于其自身,任意数与其自身异或都为0补充:
(A ⊕ B) ⊕ C = A ⊕ (B ⊕ C)  //结合律
(A ⊕ B) ⊕ (C ⊕ D) = A ⊕ B ⊕ C ⊕ D  //可以去掉括号
A ⊕ B ⊕ C ⊕ D = A ⊕ C ⊕ B ⊕ D  //可以随意交换
即,只要参与异或运算的成员不变,任意交换异或顺序,结果都一样

之前在(https://www.jianshu.com/p/99d87c778b24)推导过的结论也可以由上述结论推出:

若f ⊕ m = G,则:
f ⊕ G = m //推导: f ⊕ G = f ⊕ (f ⊕ m) = f ⊕ f ⊕ m = 0 ⊕ m = m)
m ⊕ G = f //同上

综上所述,数组中若存在重复两次的数i,则其异或结果必为0.因此遍历数组,将所有元素异或,最后剩下的必定是出现单次的数.


int singleNumber(vector<int>& nums) {for (int i = 1; i < nums.size(); i++) {  //遍历数组nums[0] ^= nums[i];  //直接用第0号存储异或结果,节省空间}return nums[0];
}

py

class Solution:def singleNumber(self, nums):""":type nums: List[int]:rtype: int"""res = nums[0]for i in range(1, len(nums)):res ^= nums[i]return res

这篇关于136. Single Number 找数组只出现一次的数字的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1083561

相关文章

从去中心化到智能化:Web3如何与AI共同塑造数字生态

在数字时代的演进中,Web3和人工智能(AI)正成为塑造未来互联网的两大核心力量。Web3的去中心化理念与AI的智能化技术,正相互交织,共同推动数字生态的变革。本文将探讨Web3与AI的融合如何改变数字世界,并展望这一新兴组合如何重塑我们的在线体验。 Web3的去中心化愿景 Web3代表了互联网的第三代发展,它基于去中心化的区块链技术,旨在创建一个开放、透明且用户主导的数字生态。不同于传统

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

usaco 1.2 Name That Number(数字字母转化)

巧妙的利用code[b[0]-'A'] 将字符ABC...Z转换为数字 需要注意的是重新开一个数组 c [ ] 存储字符串 应人为的在末尾附上 ‘ \ 0 ’ 详见代码: /*ID: who jayLANG: C++TASK: namenum*/#include<stdio.h>#include<string.h>int main(){FILE *fin = fopen (

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while

题目1380:lucky number

题目1380:lucky number 时间限制:3 秒 内存限制:3 兆 特殊判题:否 提交:2839 解决:300 题目描述: 每个人有自己的lucky number,小A也一样。不过他的lucky number定义不一样。他认为一个序列中某些数出现的次数为n的话,都是他的lucky number。但是,现在这个序列很大,他无法快速找到所有lucky number。既然

C语言:柔性数组

数组定义 柔性数组 err int arr[0] = {0}; // ERROR 柔性数组 // 常见struct Test{int len;char arr[1024];} // 柔性数组struct Test{int len;char arr[0];}struct Test *t;t = malloc(sizeof(Test) + 11);strcpy(t->arr,

C 语言基础之数组

文章目录 什么是数组数组变量的声明多维数组 什么是数组 数组,顾名思义,就是一组数。 假如班上有 30 个同学,让你编程统计每个人的分数,求最高分、最低分、平均分等。如果不知道数组,你只能这样写代码: int ZhangSan_score = 95;int LiSi_score = 90;......int LiuDong_score = 100;int Zhou

计算数组的斜率,偏移,R2

模拟Excel中的R2的计算。         public bool fnCheckRear_R2(List<double[]> lRear, int iMinRear, int iMaxRear, ref double dR2)         {             bool bResult = true;             int n = 0;             dou

C# double[] 和Matlab数组MWArray[]转换

C# double[] 转换成MWArray[], 直接赋值就行             MWNumericArray[] ma = new MWNumericArray[4];             double[] dT = new double[] { 0 };             double[] dT1 = new double[] { 0,2 };

PHP7扩展开发之数组处理

前言 这次,我们将演示如何在PHP扩展中如何对数组进行处理。要实现的PHP代码如下: <?phpfunction array_concat ($arr, $prefix) {foreach($arr as $key => $val) {if (isset($prefix[$key]) && is_string($val) && is_string($prefix[$key])) {$arr[