【鬼才算法】只出现一次的数字

那些令人拍案叫绝的算法【1】

Single Number I

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？
示例一：

1 2	输入：[2,2,1] 输出：1

示例二：

1 2	输入：[4,1,2,1,2] 输出：4

正确解法：利用异或运算的交换律，将数组中的所有数进行比较，因为交换律，将数组中的各个值交换位置后，相同的值异或结果为1，只出现一次的值不断与1异或，最后被留下来。

public int  singleNumber(int[] nums){
        for (int i=1;i<nums.length;i++){
            nums[0]^=nums[i];
        }
        return nums[0];
    }

鬼才解法：将数组中所有不同的值取出来，求和之后乘以2，减去原数组求和

1
2
3

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return sum(set(nums))*2-sum(nums)    #set() 函数创建一个无序不重复元素集

Single Number II

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现三次。找出那个只出现了一次的元素。
说明：你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？
示例一：

1 2	输入：[2,2,3,2] 输出：3

示例二：

1 2	输入：[0,1,0,1,0,1,99] 输出：99

解法：与上同理，取出无序不重复元素集求和乘3，减去原数组和，最后除以2

1
2
3

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return (sum(set(nums))*3-sum(nums))//2      # "/" 为浮点数除法，返回浮点结果 "//" 表示整数除法，返回不大于结果的一个最大整数

算法出处：Leetcode
Single Number I
Single Number II