数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学区间内出现次数最多的除数
设x和y是两个数。在这种情况下，如果y除以x余数为零，则称x是y的除数。区间内出现次数最多的除数是指在这个区间内，作为最大数量的元素的除数的数字。
问题陈述
给定一个区间[a, b]。找到包括a和b在内的范围内的出现次数最多的除数，但不包括'1'。如果所有除数的出现次数相同，则返回1。
示例1
Input [2, 5]
Output 2
解释 − 2的除数 = {1, 2}，3的除数 = {1, 3}，4的除数 = {1, 2, 4}，5的除数 = {1, 5}。2是出现次数最多的除数。
示例2
Input [2, 5]
Output 2
解释 − 2的除数 = {1, 2}，3的除数 = {1, 3}，4的除数 = {1, 2, 4}，5的除数 = {1, 5}。2是出现次数最多的除数。
方法1：暴力法
解决这个问题的暴力法是找到区间内所有数字的所有除数，并将它们与它们的出现次数一起存储在一个映射中。
算法
过程 divisors (num)
对于 i = 1 到 n1/2+1
如果 num%i == 0
如果 num/i == i
如果映射中不存在i，则插入(i, 1)
否则 map[i]++
否则
如果映射中不存在i，则插入(i, 1)
否则 map[i]++
如果映射中不存在num/i，则插入(num/i, 1)
否则 map[num/i]++
过程 maxDivisors (a, b)
对于 n = a 到 b
divisors (n)
map.erase(1)
divisor = 1, count = int_min
对于映射中的每个元素 it
如果 it.value > count
count = it.value
divisor = it.key
示例：C++ 实现
在下面的程序中，我们在divisors()函数中找到每个数字的除数，在maxdivisor()函数中找到出现次数最多的除数。
#include <bits/stdc++.h>
using namespace std;
// map storing occurrence of each divisor
unordered_map<int, int> occ;
// function to find all the divisors of a number and store it in map
void divisors(int num){
for (int i = 1; i <= (sqrt(num) + 1); i++) {
// checking if i is divisor of num
if (num % i == 0) {
// checking if num has identical divisors i.e. if i*i == num
// if identical divisors then save only one
if (num / i == i) {
if (occ.find(i) == occ.end()) {
occ.insert(make_pair(i, 1));
}
else{
occ[i]++;
}
}
else{
// saving divisor i
if (occ.find(i) == occ.end()) {
occ.insert(make_pair(i, 1));
}
else{
occ[i]++;
}
// saving the divisor of num corresponding to i
if (occ.find(num / i) == occ.end()) {
occ.insert(make_pair(num / i, 1));
}
else{
occ[num / i]++;
}
}
}
}
}
// function to find maximum occurring divisor in an interval
int maxDivisor(int a, int b){
for (int n = a; n <= b; n++){
divisors(n);
}
// deleting all occurrences of 1 as 1 is not to be returned until the interval is [1,1]
occ.erase(1);
// divisor set as 1 for edge case scenario when interval is [1,1]
int div = 1, cnt = INT_MIN;
for (auto it = occ.begin(); it != occ.end(); it++) {
if (it->second > cnt) {
cnt = it->second;
div = it->first;
}
}
return div;
}
int main(){
int a = 4, b = 7;
cout << "For the interval [" << a << ", " << b << "] maximum occurring divisor = ";
cout << maxDivisor(a, b);
return 0;
}
输出
For the interval [4, 7] maximum occurring divisor = 2
时间复杂度 − O(n3/2)，因为对于区间中的每个数字，为了找到除数，会执行复杂度为O(n1/2)的循环。
空间复杂度 − O(n)，映射空间。
方法2
上述方法可以通过减少填充映射（包含每个除数的出现次数）的时间来进一步优化。与其查找每个数字的除数，不如通过对区间的下界和上界进行计算来了解区间内每个除数的出现次数。
让我们以区间[2, 5]为例。
可能的除数集合是从1到5。因此，1的出现次数 = 5/1 - 2/1 +1 = 4。2的出现次数 = 5/2 - 2/2 + 1 = 2。3的出现次数 = 5/3 - 2/3 = 1。4的出现次数 = 5/4 - 2/4 = 1。5的出现次数 = 5/5 - 2/5 = 1。
以上可以形式化为：
如果 lower-bound%divisor == 0 则 occ = upper-bound/divisor - lower-bound/divisor + 1
否则 occ = upper-bound/divisor - lower-bound/divisor
算法
过程 maxDivisor (a, b)
对于 i = 2 到 b
如果 a%i == 0
times = b/i - a/i +1
否则
times = b/i - a/i
map.insert(i, times)
divisor = 1, count = int_min
对于映射中的每个元素 it
如果 it.value > count
count = it.value
divisor = it.key
示例：C++ 实现
在下面的程序中，我们不是查找数字的除数，而是反过来，对于每个除数，我们查找它在区间中存在多少倍数。
#include <bits/stdc++.h>
using namespace std;
// function to find maximum occurring divisor in an interval
int maxDivisor(int a, int b){
// map used to store occurrences of divisors
unordered_map<int, int> occ;
for (int i = 2; i <= b; i++){
int times;
if (a % i == 0){
times = (b / i) - (a / i) + 1;
}
else{
times = (b / i) - (a / i);
}
occ.insert(make_pair(i, times));
}
// divisor set as 1 for edge case scenario when interval is [1,1]
int div = 1, cnt = INT_MIN;
for (auto it = occ.begin(); it != occ.end(); it++){
if (it->second > cnt){
cnt = it->second;
div = it->first;
}
}
return div;
}
int main(){
int a = 1, b = 10;
cout << "For the interval [" << a << ", " << b << "] maximum occurring divisor = ";
cout << maxDivisor(a, b);
return 0;
}
输出
For the interval [1, 10] maximum occurring divisor = 2
方法3
观察到解决这个问题的一个非常简单的解决方案如下：
在大小>1的任何区间中，一半的数字（每个偶数）将具有2作为它们的除数。
因此，它可以按如下方式使用。
算法
过程 maxDivisors (a, b)
如果 a == b
ans = a
否则
ans = 2
示例：C++ 实现
在下面的程序中，我们实现了这样的观察结果：每个偶数都有2作为除数。
#include <bits/stdc++.h>
using namespace std;
// function to find the maximum occurring divisor in an interval
int maxDivisor(int a, int b){
if (a == b){
return a;
} else {
return 2;
}
}
int main(){
int a = 1, b = 10;
cout << "For the interval [" << a << ", " << b << "] maximum occurring divisor = ";
cout << maxDivisor(a, b);
return 0;
}
输出
For the interval [1, 10] maximum occurring divisor = 2
结论
总之，为了找到区间内出现次数最多的除数，我们可以使用上述方法，其时间复杂度从O(n3/2)到O(1)，空间复杂度从O(n)到O(1)。
浏览量：129
