資料結構
網路
關係型資料庫管理系統 (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
