LeetCode刷题（10）～只出现一次的数字

题目描述

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

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

示例 2:

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

解答 By 海轰

提交代码（暴力解法）

int singleNumber(vector<int> &nums)
{
  int len = nums.size();
  int j;
  int i;
  for (i = 0; i < len - 1; ++i)
  {
    for (j = i + 1; j < len; ++j)
    {
      if (nums[i] != 0)
      {
        if (nums[j] == nums[i])
        {
          nums[i] = 0;
          nums[j] = 0;
          break;
        }
      }
      else
      {
        break;
      }
    }
    if (j == len)
      break;
  }
  return nums[i];
}

运行结果

其他解答

• ​​官方​​
• ​​其他​​

方法一：异或【非常巧妙】

int singleNumber(vector<int>& nums) {
     for(int i=1;i<nums.size();++i)
         nums[0]^=nums[i];
    
    return nums[0];
    }

运行结果

方法二：set

int singleNumber(vector<int>& nums) {
        set<int> a;
    int sum1=0;
    int sum2=0;
    for(int i=0;i<nums.size();++i)
    {
      a.insert(nums[i]);
      sum2+=nums[i];
    }    
    for(set<int>::iterator it=a.begin();it!=a.end();++it)
    {
      sum1+=*it;
    }
    return 2*sum1-sum2;
    }

运行结果

方法三：哈希

int singleNumber_3(vector<int> &nums)
{
  unordered_map<int, int> a;
  for (int i = 0; i < nums.size(); ++i)
  {
    a[nums[i]]++;
  }
  unordered_map<int, int>::iterator it = a.begin();
  for (; it != a.end(); ++it)
    if (it->second == 1)
      return it->first;
  return 0;
}

C++完整测试代码

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <set>
using namespace std;
// 方法一： 暴力解法
int singleNumber_1(vector<int> &nums)
{
  int len = nums.size();
  int j;
  int i;
  for (i = 0; i < len - 1; ++i)
  {
    for (j = i + 1; j < len; ++j)
    {
      if (nums[i] != 0)
      {
        if (nums[j] == nums[i])
        {
          nums[i] = 0;
          nums[j] = 0;
          break;
        }
      }
      else
      {
        break;
      }
    }
    if (j == len)
      break;
  }
  return nums[i];
}
// 方法二：异或
int singleNumber_2(vector<int> &nums)
{
  for (int i = 1; i < nums.size(); ++i)
    nums[0] ^= nums[i];

  return nums[0];
}
// 方法三：哈希表
int singleNumber_3(vector<int> &nums)
{
  unordered_map<int, int> a;
  for (int i = 0; i < nums.size(); ++i)
  {
    a[nums[i]]++;
  }
  unordered_map<int, int>::iterator it = a.begin();
  for (; it != a.end(); ++it)
    if (it->second == 1)
      return it->first;
  return 0;
}
// 方法四：
int singleNumber_4(vector<int> &nums)
{
  set<int> a;
  int sum1 = 0;
  int sum2 = 0;
  for (int i = 0; i < nums.size(); ++i)
  {
    a.insert(nums[i]);
    sum2 += nums[i];
  }
  for (set<int>::iterator it = a.begin(); it != a.end(); ++it)
  {
    sum1 += *it;
  }
  return 2 * sum1 - sum2;
}
int main()
{

  vector<int> a;

  a.push_back(1);
  a.push_back(1);
  a.push_back(2);
  a.push_back(2);
  a.push_back(3);

  // 各个方法测试 注意 同时使用所有方法 可能结果不正确 建议一个方法一个测试
  // cout << singleNumber_1(a)<<endl;// 方法一
  // cout << singleNumber_2(a)<<endl;// 方法二
  cout << singleNumber_3(a) << endl; // 方法三
  //cout << singleNumber_4(a)<<endl;// 方法四

  return 0;
}