[LeetCode]169. Majority Element

2019-11-06 06:58:42

字体：大中小

来源：转载

供稿：网友

[LeetCode]169. Majority Element

题目描述

这里写图片描述

思路

遍历计数，返回大于n/2的值 update1 既然数的数目超过n/2，那数必然是中位数，排序之后去num[n/2] update2 分治算法，类似快排的思路，见代码

代码

class Solution {public: int majorityElement(vector<int>& nums) { unordered_map<int, int> counts; for (auto &p : nums){ ++counts[p]; } int flag = floor(nums.size() / 2); for (auto &p : counts){ if (p.second > flag) return p.first; } }};

update1

class Solution {public: int majorityElement(vector<int>& nums) { sort(nums.begin(), nums.end()); int n = nums.size(); return nums[n / 2]; }};

update2

class Solution {public: int majority(vector<int>& nums, int left, int right) { if (left == right) return nums[left]; int mid = left + ((right - left) >> 1); int lm = majority(nums, left, mid); int rm = majority(nums, mid + 1, right); if (lm == rm) return lm; return count(nums.begin() + left, nums.begin() + right + 1, lm) > count(nums.begin() + left, nums.begin() + right + 1, rm) ? lm : rm; } int majorityElement(vector<int>& nums) { return majority(nums, 0, nums.size() - 1); }};

上一篇：机器学习实战——个人学习笔记

下一篇：单链表反转