Fork me on GitHub

leetcode之136. 只出现一次的数字

发表于 | 分类于
字数统计 275 字 | 阅读时长 1 分钟

题目描述：

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

说明：

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

示例 1:

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

示例 2:

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

解题思路一：

时间复杂度：$O(logn)$,空间复杂度：$O(1)$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int i;
        if(nums.size() == 1) return nums[0];
        
        sort(nums.begin(), nums.end());
        
        for(i = 0; i < nums.size(); i+= 2)
        {
            if(nums[i] != nums[i+1])
                 break;
        }
        
        return nums[i];
    }
};

解题思路二：

时间复杂度：$O(n)$,空间复杂度：$O(n)$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
int singleNumber(vector<int>& nums)
{ 
  map<int,int> mp;
  int result = 0;
  for(int i = 0; i < nums.size();i++)
  {
    if(!mp.count(nums[i])) mp[nums[i]] = 1;
    else mp[nums[i]] += 1;
  }
  for(int j = 0 ;j < nums.size();j++)
  {
    if(mp[nums[j]] == 1) 
    {
      result = nums[j];
      break;
    }
  }
  return result;
}
};