C++ LeetCode169：求众数

前言
现在在集中看分治法，所以这道题现在只实现两种解法：

1. 暴力解法：二层循环遍历序列，对元素进行计数，将结果>n/2的数返回。时间复杂度为O(n^2)
2. 分治法：将序列从中间一分为二，求出左、右最多的数，如果两者相等，则直接返回这个数；如果两者不相等，再分别遍历序列求出这两个数在整个序列中含有的数量，返回较大的那个数。时间复杂度为O(nlong(n))

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

示例 1:
输入: [3,2,3]
输出: 3

示例 2:
输入: [2,2,1,1,1,2,2]
输出: 2

实现方法
一、暴力法

class Solution1 {
public:
	int majorityElement(vector<int>& nums) {
		int count;
		int n = nums.size();
		for (int i = 0; i < n; i++) {
			count = 0;
			for (int j = 0; j < n; j++) {
				if (nums[i] == nums[j])
					count++;
			}
			if (count > n / 2)
				return nums[i];
		}
	}
};

二、分治法

class Solution2 {
public:
	int binaryMajorityElement(vector<int> a, int left, int right) {
		int majLeft, majRight;
		int center;
		int leftCount = 0, rightCount = 0;

		//判断递归终止条件
		if (left == right)
			return a[left];
		else {
			center = (left + right) / 2;
			majLeft = binaryMajorityElement(a, left, center);
			majRight = binaryMajorityElement(a, center + 1, right);
			if (majLeft == majRight)
				return majLeft;
			else {
				for (int i = left; i <= right; i++) {
					if (a[i] == majLeft)
						leftCount++;
					if (a[i] == majRight)
						rightCount++;
				}
				return leftCount > rightCount ? majLeft : majRight;
			}
		}
	}
	int majorityElement(vector<int>& nums) {
		return binaryMajorityElement(nums, 0, nums.size() - 1);
	}
};

三、排序后遍历

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        //先将数组排序
        sort(nums.begin(),nums.end());
        int max=1,count=1,flag=0;
        //循环遍历，计数，记录出现最多的数
        for(int i=0;i<nums.size()-1;i++){
            if(nums[i+1]==nums[i]){
                count++;
            }else{
                count=1;
            }
            if(count>max){
                max=count;
                flag=i;
            }
        }
        return nums[flag];
    }
};

总结
对于这道题，因为题目假设一定有解，所以分治法可以求出对应解。如果不一定有解的情况下，分治法还需要更多的判断条件。