只出现一次的元素

题目地址：https://leetcode-cn.com/problems/single-number/

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

说明：

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

示例 1:

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

示例 2:

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

题目信息

输入：整数数组（只有一个数单个，其他数全部是两次的数组）

输出：整数（那个单个的数）

额外：时间复杂度O(n)，空间复杂度O(1)

思考

一开始看漏了信息以为只有数组里只有一个不重复其他都是重复不限次数，忽略了重复只有2次。所以想到的只有万能的map计数，无论是找出现次数最多的还是出现一次的啥都可以。但并不满足空间复杂度，为了满足空间复杂度不使用额外记录那就是暴力扫描n^2，说到扫描就还对应一个更优的方式就是排序后再扫描nlogn但这两种也都不满足线性的时间复杂度。（记得上一篇判断数组是否有重复也有这几种思路使用容器或者双指针扫描）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//方式一：Map计数
public int singleNumber(int[] nums) {
    //定义map存<数字i,计数count>
    Map<Integer, Integer> map = new HashMap<>();
    for (Integer i : nums) {
        //如果之前存在计数则加一否则计为第一个
        Integer count = map.get(i);
        count = count == null ? 1 : ++count;
        map.put(i, count);
    }
    //计数统计结束，遍历所有key找到对应计数是1的
    for (Integer i : map.keySet()) {
        Integer count = map.get(i);
        if (count == 1) {
            return i;
        }
    }
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//方式二：扫描比较
public int singleNumber(int[] nums) {
    //排好序、定义两个指针
    Arrays.sort(nums);
    int start = 0;
    int scan = 1;
    if(nums.length == 1){
        return nums[0];
    }
    /*
      当start不等于scan时
      scan停止移动
      并且比较差距判断是否出现一次
      或者scan停止的地方已经是最后一位
      否则继续把start移动到新数字上
    */
    while(start < nums.length){
        while(nums[start] == nums[scan]){
            scan++;
        }
        if(scan - start == 1){
            return nums[start];
        }else if(scan == nums.length -1){
            return nums[scan];
        }
        start = scan;
    }
    return -1;
}

以上两种方法都没有考虑条件中重复数字只是出现两次（输入数组有且只有一个数字唯一其他都是两次），解决的是其他重复数字重复多少都可以，并找到唯一的那个数。目前来说确实在数组中找到唯一数是不可能达到既满足不使用额外空间又满足线性时间复杂度。因此一定是在给出其他重复数字都是两次这样的条件下才可以实现。在这样的条件下有一种方式比上面计数就要优一点点两次相消虽然会使用额外空间但空间与时间比起计数都优化了一点

1
2
3
4
5
6
7
8
9
10
//方式三
public int singleNumber(int[] nums) {
    Set<Integer> set = new HashSet();
    for (Integer i : nums) {
        if(!set.add(i)){
            set.remove(i);
        }
    }
    return set.iterator().next();
}

但最终是要求是时间O(n)，空间O(1)。那么只能是原地相消，扫描也不可能因为是时间O(nlogn)。只能遍历一遍并且记录到最后就只剩那一个，这个时候运算熟悉的就会想到使用异或，相同运算结果为0，累计消到最后就剩下单着的那一个

1
2
3
4
5
6
7
8
//方式四
public int singleNumber(int[] nums) {
    int len = 0;
    for (int i : nums) {
        len ^= i; 
    }
    return len;
}

总结

这一道题很容易就能想到hash表或者扫描比较的解决方法，主要就是最后利用异或运算的方式实现原地相消和线性的时间复杂度