leetcode-136-Single-Number

发表于   |  

描述

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

分析

题意是有一堆元素，基本都是成双成对的，只有一只单身狗，要写一个算法找到这个单身狗。嗯，而且题目要求时间复杂度是线性的，空间复杂度是常数。将所有元素放一起进行异或运算即可

解决方案1（Python）

1
2
3
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return reduce(lambda x, y: x^y, nums)

解决方案1(C++)

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int result = nums[0];
        for(int i = 1; i < nums.size(); i++) {
            result = result ^ nums[i];
        }
        return result;
    }
};

解决方案2(Java)

1
2
3
4
5
6
7
8
9
class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int num: nums) {
            result ^= num;
        }
        return result;
    }
}

解决方案3（Golang）

1
2
3
4
5
6
7
func singleNumber(nums []int) int {
    var result int
    for _, n := range nums {
        result = (n ^ result)
    }
    return result
}

相关问题

题目来源