資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中陣列所有對的最大模（其中 arr[i] >= arr[j]）
在這個問題中，我們得到一個包含 n 個元素的陣列。我們的任務是建立一個程式來查詢陣列所有對的最大模，其中 arr[i] >= arr[j]。
在這裡，我們需要找到 arr[i] % arr[j] 的最大值，其中 arr[i] >= arr[j]。
讓我們舉個例子來理解這個問題，
輸入 − arr[] = {3, 5, 9}
輸出 − 4
解釋 −
All possible Pairs arr[i] and arr[j], 5, 3 => 5%3 = 2 9, 3 => 9%3 = 0 9, 5 => 9%5 = 4
為了解決這個問題，一個簡單直接的方法是執行兩個巢狀迴圈，並找到每對可能的模。然後，找到它們的最大值。但是，此解決方案效率不高，因為它的複雜度將是 O(n^2) 級別。
一個有效的方法將應用於排序陣列。演算法將以以下方式應用：
對於陣列中的每個元素 arr[j]，我們將找到其倍數的值，例如 x，直到找到大於陣列最大元素的值。然後，我們將找到陣列中所有滿足 arr[i] < x 的值。找到 arr[i] % arr[j]，並在每次操作後將模值的最大值儲存在 maxModulo 變數中。
讓我們使用此解決方案解決一個示例，它將展示演算法的功能：
arr = {3, 5, 9}
arr[j] = 3 for j = 0,
x = {6, 9}
For x = 6, arr[i] = 5,
arr[i]%arr[j] = 6%5 = 2, maxModulo = 2
For x = 9, arr[i] = 9,
arr[i]%arr[j] = 9%3 = 0, maxModulo = 2
arr[j] = 5 for j = 1,
x = {10}
For x = 10, arr[i] = 9,
arr[i]%arr[j] = 9%5 = 4, maxModulo =4示例
程式用於查詢陣列所有對的最大模，其中 arr[i] >= arr[j] −
#include <bits/stdc++.h>
using namespace std;
int maxModulo(int arr[], int n) {
int maxModulo = 0;
sort(arr, arr + n);
for (int j = n - 2; j >= 0; --j) {
if (maxModulo >= arr[j])
break;
if (arr[j] == arr[j + 1])
continue;
for (int k = 2 * arr[j]; k <= arr[n - 1] + arr[j]; k += arr[j]) {
int i = lower_bound(arr, arr + n, k) - arr;
maxModulo = max(maxModulo, arr[i - 1] % arr[j]);
}
}
return maxModulo;
}
int main() {
int arr[] = {3, 5, 9};
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The maximum modulo of all pairs is "<<maxModulo(arr, n);
}輸出
The maximum modulo of all pairs is 4
更新於： 2020年6月3日
513 次檢視
廣告