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

浏览数：63 / 时间：2015年06月11日 
 1 class Solution {
 2 public:
 3     int singleNumber(int A[], int n) {
 4         int i,j;
 5         for(i=0; i<n; i++)
 6         {
 7             for(j=i+1; j<n; j++)
 8             {
 9                 if(A[j]==A[i])
10                 {
11                     int temp = A[i+1];
12                     A[i+1] = A[j];
13                     A[j] = temp;
14                     i++;
15                     break;
16                 }
17             }
18             if(j==n)
19                 return A[i];    
20         }
21     }
22 };

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

 

1 class Solution {
2 public:
3     int singleNumber(int A[], int n) {
4         int result=0;
5         for(int i=0; i<n; i++)
6             result = result ^ A[i];
7         return result;
8     }
9 };

用位异或运算实现，时间复杂度和空间复杂度均为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.,,5-wow.com

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

标签： Android iOS 移动互联 终端开发

相关文章

随机文章

您可能还喜欢

您可能还喜欢