169. 多数元素
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：nums = [3,2,3]
输出：3
示例 2：
输入：nums = [2,2,1,1,1,2,2]
输出：2
题目来源：力扣（LeetCode）
分治法思路
能否写出：不能写出，需要思路，需要视频。
时间：50分钟多
介绍：
分治法（Divide and Conquer）是一种算法设计策略，它将一个大问题分解为多个相同或相似的子问题，然后递归地解决每个子问题，最后将子问题的解合并起来得到整体的解。
分治法的一般思路如下：
分解（Divide）：将原始问题划分为多个相同或相似的子问题。通常是将问题划分为规模较小的子问题。
解决（Conquer）：递归地解决每个子问题。对每个子问题进行相同的分解过程，直到子问题规模足够小可以直接求解。
合并（Combine）：将子问题的解合并起来得到原始问题的解。将每个子问题的解合并起来得到整体的解。
分治法常用于解决具有重叠子问题和可合并子问题性质的问题。通过将问题划分为规模较小的子问题，可以降低问题的复杂度并提高算法的效率。
经典的应用例子包括归并排序、快速排序、二分查找等。在这些算法中，分治法的思想被巧妙地应用，使得问题的解决变得更加高效和简洁。
这张是我画的一部分分治逻辑，希望可以帮助理解，实在不知道怎么描述思路
红色线路为下沉路线。
蓝色线路为返回路线
绿色线路是leftMajor,rightMajor对比逻辑 ，在蓝色线路中进入对比也是对比逻辑。
// 仅是我的思路代码，leetcode上大神更厉害 class Solution { public int majorityElement(int[] nums) { return majorityElementRecursive(nums,0,nums.length-1); } public int majorityElementRecursive(int[] nums, int start, int end) { if(start==end){ return nums[start]; } int middle = start+ (end-start)/2; // int leftMajor = majorityElementRecursive(nums, start, middle); int rightMajor = majorityElementRecursive(nums,middle+1,end); //如果leftMajor与rightMajor相等，那直接返回其中一个既可 if (leftMajor == rightMajor) { return leftMajor; } //如果不相等，那要统计leftMajor/rightMajor出现的次数，在start~end之间 int leftCount = countOccurrences(nums, leftMajor, start, end); int rightCount = countOccurrences(nums, rightMajor, start, end); //哪边大取哪边，相等就随便一个返回 return leftCount > rightCount ? leftMajor : rightMajor; } private int countOccurrences(int[] nums, int target, int start, int end) { int count = 0; for (int i = start; i <= end; i++) { if (nums[i] == target) { count++; } } return count; } }
时间复杂度： O(n)
空间复杂度：O(1)
