leetcode_majority_element

发表于

难度：Easy

使用Moore Voting。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int majority = nums[0];
        int majority_count = 1;
        for(int i = 1; i < nums.size(); i++)
        {
            if(majority_count == 0)
            {
                majority = nums[i];
                majority_count = 1;
            }
            else
            {
                if(majority == nums[i])
                    majority_count++;
                else
                    majority_count--;
            }
        }
        return majority;
    }
};

运行结果：26ms，超过60.34%

使用比特位，假如2是众数，则倒数第二个比特位，出现1的次数大于一半，其他位置比特位出现的0的次数大于一半。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int ret = 0;
        for(int i = 0; i < 32; i++)
        {
            int count = 0;
            for( int j = 0; j < nums.size(); j++)
            {
                if(nums[j] & (1 << i))
                    count++;
            }
            // cout<<count<<endl;
            // cout<<ret<<endl;
            if(count > nums.size()/2)
                ret |= (1 << i);
        }
        return ret;
    }
};

运行结果：53ms，超过29.97%

使用分治法写了一下，记录众数和出现的次数。

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
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        return majority_element_sub_array(nums,0,nums.size()-1).first;
    }
    pair<int,int> majority_element_sub_array(vector<int>& nums, int left, int right)
    {
        if(left == right)
            return {nums[left],1};
        int mid = left + (right - left) / 2;
        auto first_ret = majority_element_sub_array(nums, left, mid);
        auto second_ret = majority_element_sub_array(nums, mid+1, right);
        if(first_ret.first == second_ret.first)
            return {first_ret.first, first_ret.second+second_ret.second};
        else
        {
            int first_majority = first_ret.first;
            int first_majority_count = first_ret.second;
            int second_majority = second_ret.first;
            int second_majority_count = second_ret.second;
            for(int i = left; i <= mid; i++)
            {
                if(second_majority == nums[i])
                    second_majority_count++;
            }            
            for(int i = mid+1; i <= right; i++)
            {
                if(first_majority == nums[i])
                    first_majority_count++;
            }
            if(first_majority_count > second_majority_count)
                return {first_majority,first_majority_count};
            else
                return {second_majority,second_majority_count};
        }
    }
};

运行时间：33ms，超过53.51％

代码如下：

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

运行结果：59ms，超过17.42%

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//使用map

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int,int> m;
        for(int i = 0; i < nums.size(); i++)
        {
            int val = nums[i];
            m[val]++;
            if(m[val] > nums.size()/2)
                return val;
        }
        return 0;
    }
};

运行结果：59ms，超过17.42%