只出现一次的数字 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

https://leetcode-cn.com/problems/single-number/

思路&题解

要找出数组内元素,并且只出现一次的,可以想到需要对数组进行遍历,将出现的元素放入到哈希表内,统计每个不同元素出现的个数,最后把只出现一次的元素取出即为题解。

public int singleNumber(int[] nums) {
    HashMap<Integer, Boolean> map = new HashMap<>();
    for (int n : nums) {
        if (map.containsKey(n)) {
            // 第二次出现
            map.put(n, true);
        } else {
            // 第一次出现
            map.put(n, false);
        }
    }
    int result = nums[0];
    for (Map.Entry<Integer, Boolean> entry : map.entrySet()) {
        if (entry.getValue()) {
            continue;
        }
        result = entry.getKey();
        break;
    }
    return result;
}

但是这个思路不满足题目,算法中使用map存储元素,和判断元素是否存在,不满足线性复杂度不使用额外存储空间

另一个思路是现对数组元素做排序,由于题干明确表示,数组内除了目标元素,其他都出现了两次,因此我们可以判断排序后的数组中,相邻元素不相等的即为答案。

所以需要找出一个线性复杂度的排序算法,然后还不能使用额外的存储空间。 这个就更困难了,时间复杂度满足线性的排序算法,也比较少,搜索一下可知,桶排序,计算排序满足O(n),其他还有算法是O(nlogn),O(n^2)的。

更优算法

实际上,本题的已知的最佳解法是利用位运算,结合输入数组的规律,一次遍历即可将重复的元素归零。

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

知识点分析

下面看一些位运算的基本规律,和一些可以记忆的延伸的定律,方便后续类似问题使用。

位的异或运算

也可以把异或运算叫做不进位加法,异或运算的核心是:相同为假,不同为真。

用0,1举例就是,0^0=0,1^0=1,1^1=0

进一步我们可以得到,相同两个数异或等于0,还可以得出一些交换率,比如A^B=B^A

异或归零

记住两个常用的推理结论:

  1. 归零率,相同两个数异或后为零
  2. 零和任意数进行异或还是原数字
  3. 交换率,两个数异或顺序可以交换

这两个规律的一个使用场景是,交换两个数的值,除了引入一个中间变量,还可以连续异或运算:

void swap(int a, int b) {
    a = a ^ b;
    b = b ^ a;
    a = a ^ b;
}

本题的解法也是利用了这两个规律。

将数组内所有元素做异或,根据交换率,其中出现两次的相同元素异或后为零,最后剩下的就是0,0和目标元素异或,结果仍然是目标元素。

powered by Gitbook© 小文字 更新: 2019-04-10

results matching ""

    No results matching ""