首页 > 代码库 > 【LeetCode】Single Number (2 solutions)

【LeetCode】Single Number (2 solutions)

2024-07-07 09:47:23   225人阅读

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?

 

解法一：用map记录每个元素的次数，返回次数为1的元素

class Solution {
public:
    map<int,int> m;
    int singleNumber(int A[], int n) {
        for(int i = 0; i < n; i ++)
        {
            map<int,int>::iterator it = m.find(A[i]);
            if(it == m.end())
                m.insert(map<int,int>::value_type(A[i], 1));
            else
                it->second = 2;
        }

        for(map<int,int>::iterator it = m.begin(); it != m.end(); it ++)
        {
            if(it->second == 1)
                return it->first;
        }
    }
};

 

解法二：利用异或操作的结合律。同一数字异或自己结果为0.x^x=0

class Solution 
{
public:
    
    int singleNumber(int A[], int n)
    {
        int sum = 0;
        for(int i = 0; i < n; i ++)
            sum ^= A[i];
        return sum;
    }
};

 


联系
我们