資料結構
網路
RDBMS
作業系統
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] 的最大值。
所以，基本上我們需要找到陣列中兩個元素相除時的最大余數。
讓我們舉個例子來理解這個問題，
輸入 − 陣列{3, 6, 9, 2, 1}
輸出 − 6
解釋 −
3%3 = 0; 3%6 = 3; 3%9 = 3; 3%2 = 1; 3%1 = 0 6%3 = 0; 6%6 = 0; 6%9 = 6; 6%2 = 0; 6%1 =0 9%3 = 0; 9%6 = 3; 9%9 = 0 9%2 = 1; 9%1 = 0 2%3 = 2; 2%6 = 2; 2%9 = 2; 2%2 = 0; 2%1 = 0 1%3 = 1; 1%6 = 1; 1%9 = 1; 1%2 =1; 1%1 = 0 Out the above remainders the maximum is 6.
所以，找到解決方案的一種直接方法是計算每對元素的餘數，然後找到所有餘數中的最大值。但是這種方法效率不高，因為它的時間複雜度是 n2 級別。
因此，一種有效的解決方案是利用 x%y 的值在 y>x 時最大，此時餘數為 x 的邏輯。並且在陣列的所有元素中，如果我們取兩個最大元素，則結果將是最大的。為此，我們將對陣列進行排序，然後遍歷倒數第一個和倒數第二個元素以提供結果。
示例
程式演示了我們解決方案的實現，
#include <bits/stdc++.h>
using namespace std;
int maxRemainder(int arr[], int n){
bool hasSameValues = true;
for(int i = 1; i<n; i++) {
if (arr[i] != arr[i - 1]) {
hasSameValues = false;
break;
}
}
if (hasSameValues)
return 0;
sort(arr, arr+n);
return arr[n-2];
}
int main(){
int arr[] = { 3, 6, 9, 2, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The maximum remainder on dividing two elements of the array is "<<maxRemainder(arr, n);
return 0;
}輸出
The maximum remainder on dividing two elements of the array is 6
更新於: 2020-06-03
215 次瀏覽
廣告