Brooke

一、題目

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

 

Example 1:

Input: nums = [2,2,1] Output: 1

Example 2:

Input: nums = [4,1,2,1,2] Output: 4

Example 3:

Input: nums = [1] Output: 1

 

Constraints:

• 1 <= nums.length <= 3 * 104
• -3 * 104 <= nums[i] <= 3 * 104
• Each element in the array appears twice except for one element which appears only once.

 

二、程式作法

 /*解法二 XOR*/
public class Solution
{
    public int SingleNumber(int[] nums)
    {
        int res = 0;
        foreach (var item in nums)
            res ^= item;

        return res;
    }
}

/*解法一 sort*/
/*
public class Solution
{
    public int SingleNumber(int[] nums)
    {
        List<int> list = new List<int>();

        for (int i = 0; i < nums.Length; i++)
            list.Add(nums[i]);
        list.Sort();

        for (int i = 0; i < list.Count - 1; i += 2)
        {
            if (list[i] != list[i + 1])
                return list[i];
        }
        return list[list.Count - 1];
    }
}
*/

 

三、思路筆記

一陣列中，找出唯一只出現一次的元素值。

解法一，

先對陣列作排列，然後從頭開始每兩個兩個歷遍比較，

如果發現兩者不一樣時，則其中一個元素只出現一次。

解法二，

利用 XOR 的特性，兩者相同為0，不同為1，

所以將陣列裡所有的元素都 XOR 一遍之後，

最後留下來的值就是元素只出現一次的那個值。