程序分享--常见算法/编程面试题：多数元素

关注我，持续分享逻辑思维&管理思维&面试题； 可提供大厂面试辅导、及定制化求职/在职/管理/架构辅导；
有意找工作的同学，请参考博主的原创：《面试官心得--面试前应该如何准备》，《面试官心得--面试时如何进行自我介绍》， 《做好面试准备，迎接2024金三银四》。
或关注博主免费专栏【程序员宝典--常用代码分享】里面有大量面试涉及的算法或数据结构编程题。

-------------------------------------正文----------------------------------------

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：
输入：nums = [3,2,3]
输出：3

示例 2：
输入：nums = [2,2,1,1,1,2,2]
输出：2

-------------------------------------答案----------------------------------------

class Solution {
    static int count(vector<int>& arr,int x,int h,int l) {
        int sum = 0;
        for(int i = l;i <= h;i++) {
            if(arr[i] == x) {
                sum++;
            }
        }
        return sum;
    }
    static int f(vector<int>& nums,int h,int l) {
        if(h == l) {
            return nums[h];
        }
        int mid = (h+l)/2;
        int m_bound = (h-l+1)/2;
        int right_m = f(nums,h,mid+1);
        int left_m = f(nums,mid,l);
        if(count(nums,left_m,h,l) > m_bound) {
            return left_m;
        }
        if(count(nums,right_m,h,l) > m_bound) {
            return right_m;
        }
        return 0;
    }
public:
    static int majorityElement(vector<int>& nums) {
        return f(nums,nums.size()-1,0);
    }
};

感兴趣的同学辛苦 关注/点赞 ，持续分享逻辑、算法、管理、技术、人工智能相关的文章。

博主其它经典原创：《管理心得--如何高效进行跨部门合作》，《技术心得--如何成为优秀的架构师》、《管理心得--如何成为优秀的架构师》、《管理心理--程序员如何选择职业赛道》，及
《C#实例：SQL如何添加数据》，《C#实战分享--爬虫的基础原理及实现》欢迎大家阅读。