首页 > 代码库 > LeetCode:signal_number题解

LeetCode:signal_number题解

一、题目:这道题是说给你一个数组,其中的数有两个是相同的也可以说是成对的,只有一个例外,所以题目说找出光棍数(signal number)

二、分析:这道题,它说不能再使用额外的内存,而且得是线性O(n)的复杂度其实这个是有技巧的,位运算( ^ )

例如:

        Array[5]={2,4,3,4,2}

                        010

                        100

                        011

                        100

                      ^ 010

                    -----------

                   =   011

故可得解

class Solution {
public:
    int singleNumber(int A[], int n) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        int flag = 0;
        while(n){
            flag ^= A[n];
        }
        return flag;
    }
};


LeetCode:signal_number题解