leetcode-137-Single-Number-II

发表于   |  

描述

Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

1
2
Input: nums = [2,2,3,2]
Output: 3

Example 2:

1
2
Input: nums = [0,1,0,1,0,1,99]
Output: 99

Constraints:

  • 1 <= nums.length <= 3 * 104
  • -231 <= nums[i] <= 231 - 1
  • Each element in nums appears exactly three times except for one element which appears once.

分析

很有意思的一道题，与上一道题leetcode-137-Single-Number不同的是，这里的元素是三个为一组。可以用位运算，将所有的数字看作二进制的数，把所有的数字在每一位出现的次数加起来，如果是3的倍数，那么要找的那个数在该位上就是0，否则是1

解决方案1（Python）

1
2
3
4
5
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        frequency = collections.Counter(nums)
        result = [num for num, occ in frequency.items() if occ == 1][0]
        return result

解决方案2(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int i_num = 0;
        int result;
        
        for(int i = 0; i < 32; i++) {
            for(int j = 0; j < nums.size(); j++) {
                i_num += (nums[j]>>i) & 1;
            }
            result |= (i_num % 3) << i;
            i_num = 0;
        }
        return result;
    }
};

相关问题

题目来源