用^(异或）运算符判断数字的唯一性

发表于2020-03-23更新于2021-03-14

Leetcode:

问题描述：

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

说明：

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

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

Leetcode

我的思路：

先将数组排序，再遍历
code：

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
30
31
32
33
34
35
int singleNumber(int* nums, int numsSize){
    int a;
    void bubbleSort(int *dataArray,int n){//冒泡
    int flag = 0;
    int i,j,temp;
    for(i = 0;i < n - 1;i++){
        flag == 0;
        for(j = 0;j < n  - 1;j++){	
            if(dataArray[j] > dataArray[j + 1]){
                flag = 1;
                temp = dataArray[j];
                dataArray[j] = dataArray[j + 1];
                dataArray[j + 1] = temp;
                }
        }
        if(flag == 0) break;
    }
}

    bubbleSort(nums,numsSize);
    if(numsSize==1){
        a=nums[0];
    }else
    if(nums[0]!=nums[1]){
        a=nums[0];
    }else
    if(nums[numsSize-1]!=nums[numsSize-2]){
        a=nums[numsSize-1];
    }else
    for(int i=1;i<numsSize-2;i++){
        if(nums[i]!=nums[i-1]&&nums[i]!=nums[i+1])
        a=nums[i];
    }
    return a;
}

网上思路：

看了解析，发现使用我以前从未使用过的亦或运算符^可以轻松解决这个问题:

1
2
3
4
5
6
7
8
int singleNumber(int* nums, int numsSize){
    int t=nums[0];
    for(int i=1;i<numsSize;i++){
        t=t^nums[i];
    }
    return t;

}

总结:

我的思路，在提交时说超时。。。明明时间复杂度少于O(n^2)呀。
不过异或运算是真是高效。