[LeetCode OJ] Single Number之一 ——Given an array of integers, every element appears twice except for one. Find that single one.

 class Solution {

 public:

     int singleNumber(int A[], int n) {

         int i,j;

         for(i=; i<n; i++)

         {

             for(j=i+; j<n; j++)

             {

                 if(A[j]==A[i])

                 {

                     int temp = A[i+];

                     A[i+] = A[j];

                     A[j] = temp;

                     i++;

                     break;

                 }

             }

             if(j==n)

                 return A[i];

         }

     }

 };

上面的是传统方法，时间复杂度是O(n²)，空间复杂度是O(1)。

 class Solution {

 public:

     int singleNumber(int A[], int n) {

         int result=;

         for(int i=; i<n; i++)

             result = result ^ A[i];

         return result;

     }

 };

用位异或运算实现，时间复杂度和空间复杂度均为O(1).

运用了异或运算具有交换律和结合律的性质。

交换律： a^b = b^a

结合律： (a^b)^c = a^(b^c)

另外，a^a=0。

巴特西

[LeetCode OJ] Single Number之一 ——Given an array of integers, every element appears twice except for one. Find that single one.

最新文章

热门文章