Step 1 题解

Step 1-1 描述

现在有一个整数类型的数组，数组中素只有一个元素只出现一次，其余的元素都出现两次。

Step 1-2 注意

你需要给出一个线性时间复杂度的算法，你能在不使用额外内存空间的情况下解决这个问题么？

1-2-1 线性时间复杂度

如果一个算法的时间复杂度为O(n)，则称这个算法具有线性时间，或O(n)时间。非正式地说，这意味着对于足够大的输入，运行时间增加的大小与输入成线性关系。
例如，一个计算列表所有元素的和的程序，需要的时间与列表的长度成正比。

Step 2 解题（JAVA）

考虑到
  1. 只有一个元素只出现一次，其余的元素都出现两次
  2. 线性时间复杂度
  3. 不使用额外内存空间
所以设计的算法需要线性处理只有一个出现一次的数字
那有没有一个可以抵消掉复现数字的算法呢？
没错，那就是相同取0，相异取1的异或运算！
异或运算
如果a、b两个值不相同，则异或结果为1。如果a、b两个值相同，异或结果为0。
 
import java.util.*;


public class Solution {
    /**
     * 
     * @param A int整型一维数组 
     * @return int整型
     */
    public int singleNumber (int[] A) {
        // write code here
        int result = 0;
        int n=A.length;//length() 方法用于返回字符串的长度,空字符串的长度返回 0。

        for (int i = 0; i < n; ++i) {
            result ^= A[i];
        }
        return result;
    }
}