Single Number系列

发表于 | 分类于 | 浏览 次

Single Number系列

Single Number

Given a non-empty 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?

Example 1:

1
2
Input: [2,2,1]
Output: 1

Example 2:

1
2
Input: [4,1,2,1,2]
Output: 4

可能的解法有：排序后判断元素出现次数。

解法1：排序

排序后查找每个元素是否只出现了一次，直到找到那个只出现了一次的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        quickSort(nums, 0, nums.size() - 1);
        for(int i=0;i<nums.size();++i){
            if(i < nums.size()-1 && nums[i]!= nums[i+1]){
                return nums[i];
            }else{
                ++i;
            }
        }
        return nums[nums.size()-1];
    }
    
    void quickSort(vector<int>& nums, int lo, int hi){
        if(lo >= hi){
            return;
        }
        int pos = partition(nums, lo, hi);
        quickSort(nums, lo, pos - 1);
        quickSort(nums, pos + 1, hi);
    }
    int partition(vector<int>& nums, int lo,  int hi){
        int i = lo - 1;
        int tmp;
        for(int j=lo;j<hi;++j){
            if(nums[j] <= nums[hi]){
                tmp = nums[j];
                nums[j] = nums[++i];
                nums[i] = tmp;
            }
        }
        tmp = nums[hi];
        nums[hi] = nums[++i];
        nums[i] = tmp;
        return i;
    }
};

时间复杂度：O(nlogn)
空间复杂度：O(logn)

解法2：位运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 这里定义了一个lambda表达式并调用该表达式
static int x = [](){ 
  ios::sync_with_stdio(false); 
  cin.tie(0); 
  return 0;  
}();
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret=0;
        for(int i=0;i<nums.size();i++){
            ret=ret^nums[i];
        }
        return ret;
    }
};

Single Number II

Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

Note:

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

Example 1:

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

Example 2:

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

解法1：

k个相同的k进制数进行无进位相加，结果一定是每一位都为0的k进制数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        vector<int> e0(32, 0);
        for(int i=0;i<nums.size();++i){
            setExclusiveOr(e0, nums[i], 3);
        }
        int res = getNumFromKSysNum(e0, 3);
        return res;
    }
    
    vector<int> getKSysNumFromNum(int value, int k){
        vector<int> res(32, 0);
        int index = 0;
        
        // low bit on left, high bit on right
        while(value !=0){
            res[index++] = value % k;
            value /= k;
        }
        return res;
    }
    
    void setExclusiveOr(vector<int>& e0, int value, int k){
        vector<int> curKSysNum = getKSysNumFromNum(value, k);
        for(int i=0;i < e0.size();++i){
            e0[i] = (e0[i] + curKSysNum[i]) % k;
        }
    }
    
    int getNumFromKSysNum(vector<int>& e0, int k){
        int res = 0;
        for(int i=e0.size()-1;i>=0;--i){
            res = res * k + e0[i];
        }
        return res;
    }
};