美文网首页
229. Majority Element II (M)

229. Majority Element II (M)

作者: Ysgc | 来源:发表于2020-11-25 00:50 被阅读0次

    Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

    Follow-up: Could you solve the problem in linear time and in O(1) space?

    Example 1:

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

    Input: nums = [1]
    Output: [1]
    Example 3:

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

    Constraints:

    1 <= nums.length <= 5 * 104
    -109 <= nums[i] <= 109


    我的答案:时间、空间复杂度O(n)

    class Solution {
    public:
        vector<int> majorityElement(vector<int>& nums) {
            int length = nums.size();
            
            unordered_map<int, int> count;
            unordered_set<int> screen_out;
            
            for (const auto& n:nums) {
                if (screen_out.find(n) == screen_out.end()) {
                    if (count.find(n) == count.end()) {
                        count[n] = 1;
                    }
                    else {
                        ++count[n];
                    }
                    if (count[n] > length/3) {
                        screen_out.insert(n);
                    }
                }
            }
            
            vector<int> ans(screen_out.begin(), screen_out.end());
            return ans;
        }
    };
    

    Runtime: 40 ms, faster than 26.49% of C++ online submissions for Majority Element II.
    Memory Usage: 16.5 MB, less than 7.86% of C++ online submissions for Majority Element II.

    有点慢

    看答案:
    https://zxi.mytechroad.com/blog/algorithms/array/leetcode-229-majority-element-ii/

    Solution: Boyer–Moore Voting Algorithm
    Time complexity: O(n)
    Space complexity: O(1)

    class Solution {
    public:
        vector<int> majorityElement(vector<int>& nums) {
            int length = nums.size();
            
            unordered_map<int, int> count;
            vector<int> ans;
            // ans.reserve(2);
            
            for (const auto& n:nums) {
                if (find(ans.begin(), ans.end(), n) == ans.end()) {
                    if (count.find(n) == count.end()) {
                        count[n] = 1;
                    }
                    else {
                        ++count[n];
                    }
                    if (count[n] > length/3) {
                        ans.push_back(n);
                        if (ans.size() == 2) break;
                    }
                }
            }
            
            return ans;
        }
    };
    

    Runtime: 32 ms, faster than 51.59% of C++ online submissions for Majority Element II.
    Memory Usage: 16.3 MB, less than 7.86% of C++ online submissions for Majority Element II.

    看了答案之后发现,最多有2个元素输出
    做了点优化


    答案Boyer-Moore算法:

    // Author: Huahua
    class Solution {
    public:
      vector<int> majorityElement(vector<int>& nums) {
        int n1 = 0;
        int c1 = 0;
        int n2 = 1;
        int c2 = 0;
        for (int num : nums) {
          if (num == n1) {
            ++c1;
          } else if (num == n2) {
            ++c2;
          } else if (c1 == 0) {
            n1 = num;
            c1 = 1;
          } else if (c2 == 0) {
            n2 = num;
            c2 = 1;
          } else {
            --c1;
            --c2;
          }
        }
        
        c1 = c2 = 0;
        for (int num : nums) {
          if (num == n1) ++c1;
          else if (num == n2) ++c2;
        }
        
        const int c = nums.size() / 3;
        vector<int> ans;
        if (c1 > c) ans.push_back(n1);
        if (c2 > c) ans.push_back(n2);
        return ans;
      }
    };
    

    Runtime: 28 ms, faster than 76.28% of C++ online submissions for Majority Element II.
    Memory Usage: 16.1 MB, less than 23.62% of C++ online submissions for Majority Element II.

    问题:
    为什么要重新计数?
    https://www.youtube.com/watch?v=FGwCv6JAZQ8


    实验了一下,果然出错了!主要是count可能会降到0,这时候有可能整个需要,有可能不需要

    然后上面的代码其实有点tricky,n1和n2需要初始化,但是要初始化成两个不一样的数字,类似前面都搜索过一段了,但是刚好两个counter都清零的结果。否则如果n1=n2=0,然后输入都是0,那么第二个for循环的第二个if就得是else if,这样也行。

    最后是,第一个for loop里面if和else if的顺序,必须把n1和n2的判断放到最前面,否则

            for (const auto& n:nums){
                if (c1 == 0) {
                    n1 = n;
                    ++c1;
                }
                else if (c2 == 0) {
                    n2 = n;
                    ++c2;
                }
                else if (n == n1) ++c1;
                else if (n == n2) ++c2;
                else {
                    --c1;
                    --c2;
                }
            }
    

    比如连续两个1输入,[1,1,...],那么第二个1就会把c2也占了,而且本身的计数也会少加了1


    cout << n << ", " << n1 << ", " << c1 << ", " << n2 << ", " << c2 << endl;
    错误结果:
    1, 1, 1, 2147483647, 0
    1, 1, 1, 1, 1
    2, 1, 0, 1, 0 <~ “那么第二个1就会把c2也占了,而且本身的计数也会少加了1”
    3, 3, 1, 1, 0
    4, 3, 1, 4, 1
    1, 3, 0, 4, 0
    1, 1, 1, 4, 0
    5, 1, 1, 5, 1
    6, 1, 0, 5, 0
    7, 7, 1, 5, 0
    1, 7, 1, 1, 1
    1, 7, 1, 1, 2
    8, 7, 0, 1, 1
    9, 9, 1, 1, 1
    10, 9, 0, 1, 0
    1, 1, 1, 1, 0
    11, 1, 1, 11, 1
    12, 1, 0, 11, 0
    13, 13, 1, 11, 0
    14, 13, 1, 14, 1
    正确结果
    1, 1, 1, 2147483647, 0
    1, 1, 2, 2147483647, 0
    2, 1, 2, 2, 1
    3, 1, 1, 2, 0
    4, 1, 1, 4, 1
    1, 1, 2, 4, 1
    1, 1, 3, 4, 1
    5, 1, 2, 4, 0
    6, 1, 2, 6, 1
    7, 1, 1, 6, 0
    1, 1, 2, 6, 0
    1, 1, 3, 6, 0
    8, 1, 3, 8, 1
    9, 1, 2, 8, 0
    10, 1, 2, 10, 1
    1, 1, 3, 10, 1
    11, 1, 2, 10, 0
    12, 1, 2, 12, 1
    13, 1, 1, 12, 0
    14, 1, 1, 14, 1


    回顾169. Majority Element

    Boyer moore的写法是:

    // https://zxi.mytechroad.com/blog/divide-and-conquer/leetcode-169-majority-element/
    class Solution {
    public:
        int majorityElement(vector<int>& nums) {
            int majority = nums.front();
            int count = 0;
            
            for (const int num : nums) {
                if (num == majority) ++count;
                else if (--count == 0) {
                    count = 1;
                    majority = num;
                }
            }
            
            return majority;
        }
    };
    

    这里的count判断和num不需要注意前后顺序,因为只有一个count

    我自己的写的版本,过了测试

    class Solution {
    public:
        int majorityElement(vector<int>& nums) {
            int majority = nums.front();
            int count = 0;
            
            for (const int num : nums) {
                if (count == 0) {
                    ++count;
                    majority = num;
                }
                else if (num == majority) ++count;
                else --count;
            }
            
            return majority;
        }
    };
    

    相关文章

      网友评论

          本文标题:229. Majority Element II (M)

          本文链接:https://www.haomeiwen.com/subject/dviriktx.html