分治法寻找众数的算法
时间: 2023-11-18 16:57:11 浏览: 57
分治法寻找众数的算法可以分为以下几个步骤:
1. 将原始数组分成两个子数组,分别递归求解左右子数组的众数。
2. 如果左右子数组的众数相同,则返回该众数。
3. 如果左右子数组的众数不同,则分别计算左右子数组中每个数在原始数组中出现的次数,返回出现次数较多的那个数作为众数。
具体实现可以参考以下代码:
```
public int majorityElement(int[] nums) {
return majorityElement(nums,0, nums.length - 1);
}
private int majorityElement(int[] nums, int left, int right) {
if (left == right) {
return nums[left];
}
int mid = left + (right - left) / 2;
int leftMajority = majorityElement(nums, left, mid);
int rightMajority = majorityElement(nums, mid + 1, right);
if (leftMajority == rightMajority) {
return leftMajority;
}
int leftCount = countInRange(nums, leftMajority, left, right);
int rightCount = countInRange(nums, rightMajority, left, right);
return leftCount > rightCount ? leftMajority : rightMajority;
}
private int countInRange(int[] nums, int num, int left, int right) {
int count = 0;
for (int i = left; i <= right; i++) {
if (nums[i] == num) {
count++;
}
}
return count;
}
```