# 136. Single Number

Given a non-empty 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?

Example 1:

```Input: [2,2,1]
Output: 1```

Example 2:

```Input: [4,1,2,1,2]
Output: 4```

```class Solution {
public int singleNumber(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int x = 0;
for (int i = 0; i < nums.length ;i++){
x = x^nums[i];
}
return x;
}
}```

# 137. Single Number II

Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

```Input: [2,2,3,2]
Output: 3```

Example 2:

```Input: [0,1,0,1,0,1,99]
Output: 99```

```class Solution {
public int singleNumber(int[] nums) {
int a = 0;
int b = 0;
for (int n : nums) {
a = (a^n) & (~b);
b = (b^n) & (~a);
}
return a;
}

}```

``` 如果是出现两次的话，用一个bit就可以
比如 b，初始为0
当5第1次出现时， b=5
当5第2次出现是， b清空为0，表示b可以去处理其他数字了
所以，最后 如果 b !=0的话，b记录的就是只出现了一次的那个数字

->公式就是 b = b xor i  或者 b = b^i

那么，如果是三次的话，香浓定理，需要用2bits进行记录

当5第一次出现的时候，b = 5, a=0,  b记录这个数字
当5第二次出现的时候，b = 0, a=5， a记录了这个数字
当5第三次出现的时候，b = 0, a=0， 都清空了，可以去处理其他数字了
所以，如果有某个数字出现了1次，就存在b中，出现了两次，就存在a中，所以返回 a|b

公式方面 ，上面两次的时候，b清空的公式是 b = b xor i
而第三次时，b要等于零，而这时a是True，所以再 & 一个a的非就可以，b = b xor & ~a
-> b = b xor i & ~ a
a = a xor i & ~b```

# 260. Single Number III

Given an array of numbers `nums`, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

Example:

```Input:  [1,2,1,3,2,5]
Output: [3,5]```

Note:

1. The order of the result is not important. So in the above example, `[5, 3]` is also correct.
2. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?
```public int[] singleNumber(int[] nums) {
int x = 0;
for ( int num :nums){
x = x ^num;
}
int [] res = new int[2];
int n = x & -x;
for (int i = 0 ; i <nums.length;i++){
if ((n & nums[i]) !=0){
res[0] ^= nums[i];
}else {
res[1] ^= nums[i];
}
}
return res;
}```
1. 先将所有的数字进行异或运算，那么得到的结果就是这两个数字的异或运算结果，并且结果不为0
2. 找到上述结果中的某个为1的位，那么，根据整个数组中这一位是1还是0，分为两个数组，第一个数组：这一位为0的数（包括重复的数和单独的一个数），第二个数组：这一位为1的数（包括重复的数和另一个单独的一个数）
3. 对这两组数分别全部异或运算处理，那么得到的两个结果就是这两个单独的数

143 篇文章24 人订阅

0 条评论

## 相关文章

### leetcode-179-Largest Number（理解规则，自定义cmp函数进行排序）

1、这道题给定一个vector，里面存放着int类型的非负整数，要求把这些非负整数拼起来，尽可能拼成一个最大的整数。

20130

### JavaScript 正则表达式上——基本语法

JavaScript种正则表达式有两种定义方式，定义一个匹配类似 <%XXX%> 的字符串

7210

### JS魔法堂：再识Number type

Brief　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　   本来只打算理解JS中0.1 + 0.2 == 0.300000000000000...

23550

### Javascript基础回顾 之(一) 类型

本来是要继续由浅入深表达式系列最后一篇的，但是最近团队突然就忙起来了，从来没有过的忙！不过喜欢表达式的朋友请放心，已经在写了:) 在工作当中发现大家对Jav...

38170

### C#基础知识系列十(集合)

本节主要是来了解学习集合，以方便在程序编写时，什么地方该选用什么集合，让程序更健壮的运行起来。在学习了解集合之前，首先需要了解一些数据结构方面的知识。下面我...

12930

### ST算法

RMQ（Range Minimum/Maximum Query），即区间最值查询。对于长度为n的数列arr，回答若干询问Q(i,j)，返回数列arr中下标在i...

23320

在前面的几篇讨论里我们初步对FP有了些少了解：FP嘛，不就是F[A]吗？也是，FP就是在F[]壳子（context）内对程序的状态进行更改，也就是在F壳子（...

20170

### R中字段抽取、字段合并、字段匹配

1、字段抽取 字段抽取，是根据已知列数据的开始和结束位置，抽取出新的列 字段截取函数：substr(x,start,stop) tel <- '1892225...

92590

198100

### 1798: [Ahoi2009]Seq 维护序列seq

1798: [Ahoi2009]Seq 维护序列seq Time Limit: 30 Sec  Memory Limit: 64 MB Submit: 2930...

31150