C语言重构【169】多数元素(2013-408)

╰半橙微兮° 2022-12-10 07:04 94阅读 0赞

文章目录

        • 所有题目源代码：[Git地址](https://github.com/ch98road/leetcode)
        • 题目
        • 方案：
          • 复杂度计算

所有题目源代码：Git地址

题目

  1. 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
  3. 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
  7. 示例 1:
  9. 输入: [3,2,3]
  10. 输出: 3
  11. 示例 2:
  13. 输入: [2,2,1,1,1,2,2]
  14. 输出: 2

方案：

  1. class Solution
  2. { 
  3. public:
  4.     int majorityElement(vector<int> &nums)
  5.     { 
  6.         map<int, int> m;
  7.         map<int, int>::iterator it;
  8.         int len = nums.size();
  9.         for (int i = 0; i < len; i++)
  10.             m[nums[i]] = m.find(nums[i]) == m.end() ? 1 : m.find(nums[i])->second + 1;
  11.         it = m.begin();
  12.         while (it != m.end())
  13.         { 
  15.             if (it->second > len / 2)
  16.             { 
  17.                 return it->first;
  18.             }
  19.             it++;
  20.         }
  21.         return -1;
  22.     }
  23. };
复杂度计算
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

发表评论

表情：
评论列表 （有 0 条评论，94人围观）

还没有评论，来说两句吧...

相关阅读

    相关 169. 多数元素

    给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 示例

    Myth丶恋晨Myth丶恋晨/ 0 赞/ 29 阅读