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 19:23:10 浏览: 27
这段代码实现了一个查找数组中的众数的算法,其中众数是指在数组中出现次数超过一半的元素。算法的实现使用了分治法,将数组分成左右两部分,分别递归求解左右两部分的众数,然后再对左右两部分的众数进行统计,判断哪一个是整个数组的众数。如果没有找到众数,则返回-1。
具体实现中,使用了一个辅助函数 count_in_range 来统计某个元素在指定区间内出现的次数。如果某个元素在整个数组中出现次数超过一半,则该元素为整个数组的众数。
需要注意的是,这个算法的时间复杂度为 O(nlogn),因为需要进行递归求解。如果要求解时间复杂度更低的众数算法,可以使用 Boyer-Moore 投票算法,时间复杂度为 O(n)。
相关问题
vector<vector<int>> threeSum(vector<int>& nums)什么意思
nums) {
vector<vector<int>> res;
sort(nums.begin(), nums.end()); // sort the array in ascending order
int n = nums.size();
for(int i=0; i<n-2; i++) {
if(i==0 || (i>0 && nums[i]!=nums[i-1])) { // skip duplicates
int lo = i+1, hi = n-1, sum = 0-nums[i];
while(lo<hi) {
if(nums[lo]+nums[hi]==sum) {
res.push_back({nums[i], nums[lo], nums[hi]});
while(lo<hi && nums[lo]==nums[lo+1]) lo++; // skip duplicates
while(lo<hi && nums[hi]==nums[hi-1]) hi--; // skip duplicates
lo++; hi--;
} else if(nums[lo]+nums[hi]<sum) lo++;
else hi--;
}
}
}
return res;
}
vector<int> twoSum(vector<int>& nums, int target)
这一个 C++ 函数,它的功能是在给定的整数数组 nums 中找到两个数的索引,使它们的和等于目标值 target。函数的定义如下:
```c++
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> map;
for (int i = 0; i < nums.size(); i++) {
int complement = target - nums[i];
if (map.count(complement)) {
return { map[complement], i };
}
map[nums[i]] = i;
}
return {};
}
```
该函数使用哈希表来快速查找数组中是否存在某个数,时间复杂度为 O(n),其中 n 是数组的长度。如果找到两个数的索引,函数会返回一个包含这两个索引的 vector<int>,否则返回一个空的 vector<int>。