我正在解決關于LeetCode的問題：
給定兩個長度均為 n 的正整數陣列 nums1 和 nums2。陣列 nums1 和 nums2 的絕對和差定義為 |nums1[i] - nums2[i]| 之和。對于每個 0 <= i < n（0 索引）。您最多可以將nums1 的一個元素替換為 nums1 中的任何其他元素，以最小化絕對和差。回傳最多替換陣列 nums1 中的一個元素后的最小絕對和差。由于答案可能很大，因此將其模數 (10^9 7) 回傳。對于輸入：
nums1=[1,7,5]，nums2=[2,3,5]，輸出：3。
我想出的代碼如下：
class Solution {
public:
int minAbsoluteSumDiff(vector<int>& nums1, vector<int>& nums2) {
if(nums1==nums2) return 0;
long long MOD=(int)1e9 7;
set<long long> s(begin(nums1),end(nums1));
long long diff=0ll, res=LLONG_MAX;
for(int i=0; i<nums1.size(); i )
diff=(diff%MOD (abs(nums1[i]-nums2[i]))%MOD)%MOD;
for(int i=0; i<nums2.size(); i ) {
long long curr=nums2[i];
auto lb=s.lower_bound(curr);
if(lb!=s.begin()) {
auto p=prev(lb);
long long prevElement=*p;
long long currsum=diff;
currsum=(currsum%MOD-(abs(nums1[i]-nums2[i]))%MOD)%MOD;
currsum=(currsum%MOD abs(curr-prevElement)%MOD)%MOD;
res=min(res, currsum);
}
if(lb!=s.end()) {
long long nextElement=*lb;
long long currsum=diff;
currsum=(currsum%MOD-(abs(nums1[i]-nums2[i]))%MOD)%MOD;
currsum=(currsum%MOD (abs(curr-nextElement))%MOD)%MOD;
res=min(res, currsum);
}
}
return res;
}
};
這適用于50/51測驗用例，但在最后一個具有大值的情況下，一些模hijinkery 會破壞它。我這樣做的原因：
currsum=(currsum%MOD-(abs(nums1[i]-nums2[i]))%MOD)%MOD;
是因為模數的分配性質：(a b) % c = ((a % c) (b % c)) % c.
我錯過了什么？
uj5u.com熱心網友回復：
這個問題是模算術的一個常見錯誤，令人驚訝的是，它與整數溢位無關（通常是這種情況），而僅僅是順序屬性與模數沒有很好地混合的結果。
你說分配屬性，(a b) % c = ((a % c) (b % c)) % c應該讓你在方程中取模。當結果相互比較時，這不再是真的。讓我們看一個更簡單的問題：
Given two arrays A and B, find the array with the smallest sum,
and return its sum modulo 9.
A = [2, 8]
B = [1, 1]
現在，答案應該是陣列 B，它的和為 2，小于 10。如果你只在最后進行取模，你會得到正確的答案：
sum(A) = 10
sum(B) = 2
sum(B) < sum(A), so return (2 % 9) == 2
但如果你在中間執行模數：
sum(A) % 9 == 1
sum(B) % 9 == 2
sum(A) % 9 < sum(B) % 9, so you return (1 % 9) == 1
由于這里的約束意味著您的總和不能溢位 long long int，因此您的問題可以通過在 return 陳述句的最后執行一個模運算來解決。
通常，如果您想要（最小和）模 p 而不是最小值（和模 p）的問題要求您不對中間結果執行模除：您必須使用足夠大的整數型別來比較真值（或在至少有一種比較真實值的方法）。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/424347.html
上一篇：全域變數是否需要更長的獲取時間？
下一篇：變換表結構