初级算法-数组-只出现一次的数字

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

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

摘一个示例做个说明.
示例 1：
输入: [2,2,1]
输出: 1

条件分析:

1. 非空整数数组 -> 不用考虑空情况
2. 一个元素一次,其余全部两次 -> 只会有一个结果
3. 线性时间复杂度,不能额外空间 -> 时间考虑,不能开辟额外空间

解决思路1:

1. 根据分析1,如果只有一个数据的话,直接返回
2. 根据分析3,要考虑时间消耗

不使用额外空间,并且数组是不可变数组,说明要考虑数据处理方式.并且要考虑时间消耗.不能多循环.所以采用位运算方式.

异或运算有以下三个性质。(好久不看书了,摘录自百度)
1.任何数和0做异或运算,结果仍是原来的数. a ^ 0 = a
2.任何数和自身做异或运算,结果都是0. a ^ a = 0
3.异或运算满足交换律和结合律. a^b^a = b^(a^a) = b^0 = b

代码实现-Swift版本:

思路1代码:

func singleNumber(_ nums: [Int]) -> Int {
    /**
     时间复杂度：O(n)，其中 n 是数组长度。只需要对数组遍历一次。
     空间复杂度：O(1)。
     */
    if nums.count == 1 {
        return nums.first!
    }
    // 0和任意数据的异或运算都是该数据本身
    var num = 0
    for item in nums {
        // 位运算,异或后,真假为真,理解为二进制即可
        num = num ^ item
    }
    
    return num
}

只出现一次的数字 位运算 提交结果.jpg

测试用例:

let array = [1]
let array = [1,1,2,2,3,4,4,5,6,5,6,7,8,9,8,9,7]

考察要点:

• 位运算
• 数组