class Solution { int count_in_range(vector<int>& nums, int target, int lo, int hi) { int count = 0; for (int i = lo; i <= hi; ++i) if (nums[i] == target) ++count; return count; } int majority_element_rec(vector<int>& nums, int lo, int hi) { if (lo == hi) return nums[lo]; int mid = (lo + hi) / 2; int left_majority = majority_element_rec(nums, lo, mid); int right_majority = majority_element_rec(nums, mid + 1, hi); if (count_in_range(nums, left_majority, lo, hi) > (hi - lo + 1) / 2) return left_majority; if (count_in_range(nums, right_majority, lo, hi) > (hi - lo + 1) / 2) return right_majority; return -1; } public: int majorityElement(vector<int>& nums) { return majority_element_rec(nums, 0, nums.size() - 1); } };
时间: 2024-02-14 13:23:11 浏览: 90
这是一个求众数(出现次数超过数组长度一半的数)的算法,采用了分治的思想。
具体实现方式是将数组分为左右两部分,分别递归求解左右两部分的众数。如果左右两部分的众数相同,则直接返回这个众数;否则,统计左右两部分中各自的众数在整个数组中出现的次数,返回出现次数较多的那个众数。
需要注意的是,递归的终止条件是 lo == hi,即数组只有一个元素时直接返回该元素作为众数。如果最后没有找到众数,则返回 -1。
阅读全文