求解众数问题,给定一个整数序列,给定一个整数序列,每个元素出现的次数称为重数,重数最大的元素称为众数,编写一个实验程序对递增有序序列求众数。例如:a={1,2,2,2,3,3,5,6,6,6,6},其众数为6,重数为4。 求解思路为:
时间: 2024-02-20 14:02:42 浏览: 113
可以使用两种方法求解众数问题。第一种方法是遍历整个序列,使用哈希表记录每个元素出现的次数,并记录出现最多次数的元素。第二种方法是利用递增有序序列的特点,使用二分法查找众数。
下面给出第二种方法的代码实现:
```
int findMode(int[] nums) {
int left = 0, right = nums.length - 1;
int mode = nums[0], maxCount = 1;
while (left <= right) {
int mid = left + (right - left) / 2;
int count = 1;
for (int i = mid - 1; i >= left && nums[i] == nums[mid]; i--) {
count++;
}
for (int i = mid + 1; i <= right && nums[i] == nums[mid]; i++) {
count++;
}
if (count > maxCount) {
maxCount = count;
mode = nums[mid];
}
if (count == maxCount && nums[mid] > mode) {
mode = nums[mid];
}
if (count > (right - left + 1) / 2) {
return mode;
}
if (count <= (right - left + 1) / 2) {
if (mid == left) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return mode;
}
```
该方法的时间复杂度为 O(nlogn),空间复杂度为 O(1)。
阅读全文