2023-09-05：請(qǐng)用go語言編寫。一個(gè)圖像有n個(gè)像素點(diǎn)，存儲(chǔ)在一個(gè)長度為n的數(shù)組arr里，
2023-09-05：請(qǐng)用go語言編寫。一個(gè)圖像有n個(gè)像素點(diǎn)，存儲(chǔ)在一個(gè)長度為n的數(shù)組arr里，
每個(gè)像素點(diǎn)的取值范圍[0,s]的整數(shù)，
請(qǐng)你給圖像每個(gè)像素點(diǎn)值加上一個(gè)整數(shù)k（可以是負(fù)數(shù)），
像素值會(huì)自動(dòng)截取到[0,s]范圍，
當(dāng)像素值<0，會(huì)更改為0，當(dāng)新像素值>s，會(huì)更改為s，
這樣就可以得到新的arr，想讓所有像素點(diǎn)的平均值最接近中位值s/2, 向下取整。
請(qǐng)輸出這個(gè)整數(shù)k, 如有多個(gè)整數(shù)k都滿足, 輸出小的那個(gè)。
1 <= n <= 10^6，
1 <= s <= 10^18。
來自華為OD。
來自左程云。
答案2023-09-05：
根據(jù)代碼和題目描述，可以將算法分為以下三種不同的方法：
方法一：暴力方法
??這種方法通過枚舉k的值來計(jì)算每個(gè)像素值加上k后的平均值，然后選擇平均值最接近中位值s/2的k。
??該方法采用兩層循環(huán)：外層循環(huán)枚舉k的取值，內(nèi)層循環(huán)計(jì)算平均值。
??時(shí)間復(fù)雜度：O(n^2)
??空間復(fù)雜度：O(1)
方法二：優(yōu)化暴力方法
??這種方法在暴力方法的基礎(chǔ)上進(jìn)行了一些優(yōu)化，采用二分查找來減少計(jì)算的次數(shù)。
??首先，確定k的取值范圍為[-s, s]，然后進(jìn)行二分查找來逼近平均值最接近中位值s/2的k。
??時(shí)間復(fù)雜度：O(n*log(s))
??空間復(fù)雜度：O(1)
方法三：正式方法（最優(yōu)解）
??這種方法是一種最優(yōu)解，通過先對(duì)數(shù)組arr進(jìn)行排序，然后使用前綴和數(shù)組pre來存儲(chǔ)累加和，以便在計(jì)算過程中快速計(jì)算區(qū)間和。
??確定k的取值范圍，根據(jù)k的正負(fù)分別進(jìn)行二分查找，得到最接近中位值s/2的k。
??時(shí)間復(fù)雜度：O(n*log(n) + log(s)*log(n))
??空間復(fù)雜度：O(n)
go完整代碼如下：
package?main
import?(
????"fmt"
????"math"
????"math/rand"
????"sort"
)
//?暴力方法
//?為了測(cè)試
func?best1(arr?[]int,?s?int)?int?{
????half?:=?s?/?2
????average?:=?-100000
????ans?:=?-s
????for?k?:=?-s;?k?<=?s;?k++?{
????????curAverage?:=?average1(arr,?k,?s)
????????if?math.Abs(float64(half-curAverage))?<?math.Abs(float64(half-average))?{
????????????average?=?curAverage
????????????ans?=?k
????????}
????}
????return?ans
}
//?暴力方法
//?為了測(cè)試
func?average1(arr?[]int,?k,?s?int)?int?{
????sum?:=?0
????for?_,?num?:=?range?arr?{
????????value?:=?num?+?k
????????if?value?<?0?{
????????????sum?+=?0
????????}?else?if?value?>?s?{
????????????sum?+=?s
????????}?else?{
????????????sum?+=?value
????????}
????}
????return?sum?/?len(arr)
}
//?優(yōu)化了一下，但不是最優(yōu)解
func?best2(arr?[]int,?s?int)?int?{
????l?:=?-s
????r?:=?s
????m?:=?0
????half?:=?s?/?2
????average?:=?-s
????ans?:=?0
????for?l?<=?r?{
????????m?=?(l?+?r)?/?2
????????curAverage?:=?average1(arr,?m,?s)
????????if?math.Abs(float64(half-curAverage))?<?math.Abs(float64(half-average))?||
????????????(math.Abs(float64(half-curAverage))?==?math.Abs(float64(half-average))?&&?m?<?ans)?{
????????????average?=?curAverage
????????????ans?=?m
????????}
????????if?curAverage?>=?half?{
????????????r?=?m?-?1
????????}?else?{
????????????l?=?m?+?1
????????}
????}
????return?ans
}
//?正式方法
//?最優(yōu)解
//?O(N?*?logN)?+?O(logS?*??logN)
func?best3(arr?[]int,?s?int)?int?{
????sort.Ints(arr)
????sum?:=?make([]int,?len(arr))
????sum[0]?=?arr[0]
????for?i?:=?1;?i?<?len(arr);?i++?{
????????sum[i]?=?sum[i-1]?+?arr[i]
????}
????l?:=?-s
????r?:=?s
????m?:=?0
????half?:=?s?/?2
????average?:=?-s
????ans?:=?0
????for?l?<=?r?{
????????m?=?(l?+?r)?/?2
????????curAverage?:=?average3(arr,?sum,?m,?s)
????????if?math.Abs(float64(half-curAverage))?<?math.Abs(float64(half-average))?||
????????????(math.Abs(float64(half-curAverage))?==?math.Abs(float64(half-average))?&&?m?<?ans)?{
????????????average?=?curAverage
????????????ans?=?m
????????}
????????if?curAverage?>=?half?{
????????????r?=?m?-?1
????????}?else?{
????????????l?=?m?+?1
????????}
????}
????return?ans
}
func?average3(arr?[]int,?pre?[]int,?k,?s?int)?int?{
????n?:=?len(arr)
????if?k?<?0?{
????????l?:=?bsZero(arr,?k)
????????sum?:=?rangeSum(pre,?l+1,?n-1)
????????return?(sum?+?(k?*?(n?-?l?-?1)))?/?n
????}?else?{
????????r?:=?bsS(arr,?k,?s)
????????sum?:=?rangeSum(pre,?0,?r-1)
????????return?(sum?+?(k?*?r)?+?(s?*?(n?-?r)))?/?n
????}
}
func?bsZero(arr?[]int,?k?int)?int?{
????ans?:=?-1
????l?:=?0
????r?:=?len(arr)?-?1
????var?m?int
????for?l?<=?r?{
????????m?=?(l?+?r)?/?2
????????if?arr[m]+k?<=?0?{
????????????ans?=?m
????????????l?=?m?+?1
????????}?else?{
????????????r?=?m?-?1
????????}
????}
????return?ans
}
func?bsS(arr?[]int,?k,?s?int)?int?{
????ans?:=?len(arr)
????l?:=?0
????r?:=?len(arr)?-?1
????var?m?int
????for?l?<=?r?{
????????m?=?(l?+?r)?/?2
????????if?arr[m]+k?>=?s?{
????????????ans?=?m
????????????r?=?m?-?1
????????}?else?{
????????????l?=?m?+?1
????????}
????}
????return?ans
}
func?rangeSum(pre?[]int,?l,?r?int)?int?{
????if?l?>?r?{
????????return?0
????}
????if?l?==?0?{
????????return?pre[r]
????}
????return?pre[r]?-?pre[l-1]
}
//?為了測(cè)試
func?randomArray(n,?s?int)?[]int?{
????arr?:=?make([]int,?n)
????for?i?:=?0;?i?<?n;?i++?{
????????arr[i]?=?randInt(0,?s)
????}
????return?arr
}
func?randInt(min,?max?int)?int?{
????return?min?+?rand.Intn(max-min+1)
}
func?main()?{
????N?:=?50
????S?:=?500
????testTimes?:=?10000
????fmt.Println("測(cè)試開始")
????for?i?:=?0;?i?<?testTimes;?i++?{
????????n?:=?randInt(1,?N)
????????s?:=?randInt(1,?S)
????????arr?:=?randomArray(n,?s)
????????ans1?:=?best1(arr,?s)
????????ans2?:=?best2(arr,?s)
????????ans3?:=?best3(arr,?s)
????????if?ans1?!=?ans2?||?ans1?!=?ans3?{
????????????fmt.Println("出錯(cuò)了！")
????????}
????}
????fmt.Println("測(cè)試結(jié)束")
}
c++完整代碼如下：
using?namespace?std;
int?average1(vector<int>&?arr,?int?k,?int?s);
int?average3(vector<int>&?arr,?vector<int>&?pre,?int?k,?int?s);
int?bsZero(vector<int>&?arr,?int?k);
int?bsS(vector<int>&?arr,?int?k,?int?s);
int?rangeSum(vector<int>&?pre,?int?l,?int?r);
int?best1(vector<int>&?arr,?int?s);
int?best2(vector<int>&?arr,?int?s);
int?best3(vector<int>&?arr,?int?s);
vector<int>?randomArray(int?n,?int?s);
void?test();
int?average1(vector<int>&?arr,?int?k,?int?s)?{
????int?sum?=?0;
????for?(int?num?:?arr)?{
????????int?value?=?num?+?k;
????????if?(value?<?0)?{
????????????sum?+=?0;
????????}
????????else?if?(value?>?s)?{
????????????sum?+=?s;
????????}
????????else?{
????????????sum?+=?value;
????????}
????}
????return?sum?/?arr.size();
}
int?average3(vector<int>&?arr,?vector<int>&?pre,?int?k,?int?s)?{
????int?n?=?arr.size();
????if?(k?<?0)?{
????????int?l?=?bsZero(arr,?k);
????????int?sum?=?rangeSum(pre,?l?+?1,?n?-?1);
????????return?(sum?+?(k?*?(n?-?l?-?1)))?/?n;
????}
????else?{
????????int?r?=?bsS(arr,?k,?s);
????????int?sum?=?rangeSum(pre,?0,?r?-?1);
????????return?(sum?+?(k?*?r)?+?(s?*?(n?-?r)))?/?n;
????}
}
int?bsZero(vector<int>&?arr,?int?k)?{
????int?ans?=?-1;
????int?l?=?0;
????int?r?=?arr.size()?-?1;
????int?m;
????while?(l?<=?r)?{
????????m?=?(l?+?r)?/?2;
????????if?(arr[m]?+?k?<=?0)?{
????????????ans?=?m;
????????????l?=?m?+?1;
????????}
????????else?{
????????????r?=?m?-?1;
????????}
????}
????return?ans;
}
int?bsS(vector<int>&?arr,?int?k,?int?s)?{
????int?ans?=?arr.size();
????int?l?=?0;
????int?r?=?arr.size()?-?1;
????int?m;
????while?(l?<=?r)?{
????????m?=?(l?+?r)?/?2;
????????if?(arr[m]?+?k?>=?s)?{
????????????ans?=?m;
????????????r?=?m?-?1;
????????}
????????else?{
????????????l?=?m?+?1;
????????}
????}
????return?ans;
}
int?rangeSum(vector<int>&?pre,?int?l,?int?r)?{
????if?(l?>?r)?{
????????return?0;
????}
????return?l?==?0???pre[r]?:?(pre[r]?-?pre[l?-?1]);
}
int?best1(vector<int>&?arr,?int?s)?{
????int?half?=?s?/?2;
????int?average?=?-100000;
????int?ans?=?-s;
????for?(int?k?=?-s;?k?<=?s;?k++)?{
????????int?curAverage?=?average1(arr,?k,?s);
????????if?(abs(half?-?curAverage)?<?abs(half?-?average))?{
????????????average?=?curAverage;
????????????ans?=?k;
????????}
????}
????return?ans;
}
int?best2(vector<int>&?arr,?int?s)?{
????int?l?=?-s;
????int?r?=?s;
????int?m?=?0;
????int?half?=?s?/?2;
????int?average?=?-s;
????int?ans?=?0;
????while?(l?<=?r)?{
????????m?=?(l?+?r)?/?2;
????????int?curAverage?=?average1(arr,?m,?s);
????????if?((abs(half?-?curAverage)?<?abs(half?-?average))
????????????||?((abs(half?-?curAverage)?==?abs(half?-?average))?&&?m?<?ans))?{
????????????average?=?curAverage;
????????????ans?=?m;
????????}
????????if?(curAverage?>=?half)?{
????????????r?=?m?-?1;
????????}
????????else?{
????????????l?=?m?+?1;
????????}
????}
????return?ans;
}
int?best3(vector<int>&?arr,?int?s)?{
????sort(arr.begin(),?arr.end());
????vector<int>?sum(arr.size());
????sum[0]?=?arr[0];
????for?(int?i?=?1;?i?<?arr.size();?i++)?{
????????sum[i]?=?sum[i?-?1]?+?arr[i];
????}
????int?l?=?-s;
????int?r?=?s;
????int?m?=?0;
????int?half?=?s?/?2;
????int?average?=?-s;
????int?ans?=?0;
????while?(l?<=?r)?{
????????m?=?(l?+?r)?/?2;
????????int?curAverage?=?average3(arr,?sum,?m,?s);
????????if?((abs(half?-?curAverage)?<?abs(half?-?average))
????????????||?((abs(half?-?curAverage)?==?abs(half?-?average))?&&?m?<?ans))?{
????????????average?=?curAverage;
????????????ans?=?m;
????????}
????????if?(curAverage?>=?half)?{
????????????r?=?m?-?1;
????????}
????????else?{
????????????l?=?m?+?1;
????????}
????}
????return?ans;
}
vector<int>?randomArray(int?n,?int?s)?{
????vector<int>?arr(n);
????for?(int?i?=?0;?i?<?n;?i++)?{
????????arr[i]?=?rand()?%?(s?+?1);
????}
????return?arr;
}
void?test()?{
????int?N?=?50;
????int?S?=?500;
????int?testTimes?=?10000;
????cout?<<?"測(cè)試開始"?<<?endl;
????for?(int?i?=?0;?i?<?testTimes;?i++)?{
????????int?n?=?rand()?%?N?+?1;
????????int?s?=?rand()?%?S?+?1;
????????vector<int>?arr?=?randomArray(n,?s);
????????int?ans1?=?best1(arr,?s);
????????int?ans2?=?best2(arr,?s);
????????int?ans3?=?best3(arr,?s);
????????if?(ans1?!=?ans2?||?ans1?!=?ans3)?{
????????????cout?<<?"出錯(cuò)了!"?<<?endl;
????????}
????}
????cout?<<?"測(cè)試結(jié)束"?<<?endl;
}
int?main()?{
????test();
????return?0;
}
