Leetcode — 只出现一次的数

1.只出现一次的数（136 – 易）

题目描述：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 :

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

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

思路：

法1：本题比较常规的解法是用集合进行记录，最终返回集合中的唯一元素，代码实现如下，但这里空间复杂度O(n)！

法2：先排序后比较有没有落单的，落单返回，时间复杂度O(nlogn)，空间复杂度O(1)。

法3：根据异或对象相同为0，不同为1的规则，可以推导出一些性质

• 0 ⊕ a = a
• a ⊕ a = 0

此外，异或满足交换律以及结合律。

代码实现：

解法1：

public int singleNumber(int[] nums) {
    HashSet set = new HashSet();
    for (int i = 0; i 

ps：这里注意迭代器和数据结构中的链表一样，有个header指针，header->next()就是链表中第一个元素…… 如下所示：

 pre  1  2  3  4

开始header指针指向pre，当执行一次iterator().next()就是返回指针所指的元素，即返回1，本题中返回那个唯一元素。

解法2:

public int singleNumber(int[] nums) {
    if (nums.length == 1) return nums[0];
    int i = 1;
    Arrays.sort(nums);
    for ( ; i 

解法3：

public int singleNumber(int[] nums) {
    int ans = 0;
    for (int i = 0; i 

2.只出现一次的数（137 – 中）

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

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

示例 :

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

输入: [0,1,0,1,0,1,99]
输出: 99

思路：

法1：和1不同的是，本题重复数字变成3个，可以用HashMap来实现计数，但时间复杂度O(n)；

法2：和案例1解法2思路相同，先排序，后比较；

法3：参考 这里 的一个解法。我们把数字放眼到二进制形式。

假如例子是 1 2 6 1 1 2 2 3 3 3,   3 个 1, 3 个 2, 3 个 3,1 个 6
1    0 0 1
2    0 1 0 
6    1 1 0 
1    0 0 1
1    0 0 1
2    0 1 0
2    0 1 0
3    0 1 1  
3    0 1 1
3    0 1 1      
看最右边的一列 1001100111 有 6 个 1
再往前看一列 0110011111 有 7 个 1
再往前看一列 0010000 有 1 个 1
我们只需要把是 3 的倍数的对应列写 0，不是 3 的倍数的对应列写 1    
也就是 1 1 0,也就是 6。

原因的话，其实很容易想明白。如果所有数字都出现了 3 次，那么每一列的 1 的个数就一定是 3 的倍数。之所以有的列不是 3 的倍数，就是因为只出现了 1 次的数多贡献出了 1。

所以所有不是 3 的倍数的列写 1（多出的数有贡献），其他列写 0（无贡献） ，就找到了这个出现 1 次的数。

本解法也可以进行推广，即是n的倍数列写1，其他列写0，找到其余元素都出现n次时，出现1次的元素。

代码实现：

解法1：

public int singleNumber(int[] nums) {
    HashMap map = new HashMap();
    for (int i = 0; i 

解答2：

public int singleNumber(int[] nums) {
    if (nums.length == 1) return nums[0];
    int i = 2;
    Arrays.sort(nums);
    for (i = 2; i 

解法3：外层循环32位二进制，可以认为时间复杂度为O(n)

public int singleNumber(int[] nums) {
    int ans = 0;
    //考虑每一位
    for (int i = 0; i >> i & 1) == 1) {
                count++;
            }
        }
        //1 

ps：注意先位运算再进行逻辑运算。java优先级口诀：单目乘除为（位）关系，逻辑三目后赋值。

• 单目：单目运算符+ –(负数) ++ — 等
• 乘除：算数单目运算符* / % + –
• 为：位移单目运算符> >>>
  • 带符号右移>>（相当于除以2）：正数右移高位补0，负数右移高位补1。
  • 无符号右移>>>：无论正数负数，高位统统补0。
• 关系：关系单目运算符> =
• 逻辑：逻辑单目运算符&& || & | ^
• 三目：三目单目运算符A > B ? X : Y
• 后：无意义，仅仅为了凑字数
• 赋值：赋值 =