文章目錄相關(guān)推薦閱讀題目描述與示例題目描述輸入描述輸出描述示例輸入輸出解題思路代碼PythonJavaCCNode JavaScriptGo時空復雜度華為OD算法/大廠面試高頻題算法練習沖刺訓練相關(guān)推薦閱讀【華為OD機考正在更新】2025年雙機位A卷真題【完全原創(chuàng)題解 | 詳細考點分類 | 不斷更新題目 | 六種主流語言PyJavaCppCJsGo】【華為OD機考】2025C2025B2024ED卷真題【完全原創(chuàng)題解 | 詳細考點分類 | 不斷更新題目】【華為OD筆試】雙機位A2025C2025B2024ED卷真題機考套題匯總【真實反饋不斷更新限時免費】【華為OD筆試】2024ED卷命題規(guī)律解讀【分析500場OD筆試考點總結(jié)】【華為OD流程】性格測試選項注意事項】題目練習網(wǎng)址【貪心】雙機位A-數(shù)字序列比大小題目描述與示例題目描述AB兩個人玩一個數(shù)字比大小的游戲在游戲前兩個人會拿到相同長度的兩個數(shù)字序列兩個數(shù)字序列不相同的且其中的數(shù)字是隨機的。AB各自從數(shù)字序列中挑選出一個數(shù)字進行大小比較贏的人得1分輸?shù)娜丝?分相等則各自的分數(shù)不變。 用過的數(shù)字需要丟棄。求A可能贏B的最大分數(shù)。輸入描述輸入數(shù)據(jù)的第1個數(shù)字表示數(shù)字序列的長度N后面緊跟著兩個長度為N的數(shù)字序列。輸出描述A可能贏B的最大分數(shù)示例輸入3 4 8 10 3 6 4輸出3解題思路這道題很明顯是一道貪心結(jié)合雙指針的題目。由于平局情況的出現(xiàn)本題難點在于我們?nèi)绾蔚剡x擇策略。很容易想到我們可以采取類似田忌賽馬的策略為了使得A贏的盡可能多每次出現(xiàn)A中元素較小的時候我們總是選擇這個較小的元素和B中盡可能大的數(shù)去分組。首先需要將兩個數(shù)組各自排序方便考慮兩個數(shù)組里的的最值情況。我們設(shè)置四個指針ia_leftia_rightib_leftib_right分別指向A、B數(shù)組中尚未比較過的元素的最小值和最大值。其初始化為ia_left0ib_left0ia_rightn-1ib_rightn-1如下圖所示在一個while循環(huán)中比較A和B中尚未比較過元素的最小值即A[ia_left]和B[ib_left]。若A[ia_left] B[ib_left]。由于選擇B中的其他數(shù)字可能會導致A[ia_left]無法獲勝故選擇該組進行比較A獲勝。# A中最小值【大于】B中最小值的情況ifA[ia_left]B[ib_left]:ans1ia_left1ib_left1A[ia_left] B[ib_left]。由于此時A中最小值小于B中的任意一個元素我們不妨采取田忌賽馬的策略讓A[ia_left]和B[ib_right]進行分組B獲勝。# A中最小值【小于】B中最小值的情況ifA[ia_left]B[ib_left]:ans-1ia_left1ib_right-1A[ia_left] B[ib_left]。這是最復雜的情況我們繼續(xù)考慮A和B中尚未比較過元素的最大值即A[ia_right]和B[ib_right]情況。若A[ia_right] B[ib_right]即以下情況若此時令A[ia_left]和B[ib_right]分組由于A[ia_right]無論怎么配對都是必勝但A[ia_left]原本可以平局的配對現(xiàn)在卻輸了故不能采取這樣的策略。故讓A[ia_right]和B[ib_right]分組A[ia_right]獲勝。# A中最小值【等于】B中最小值的情況ifA[ia_left]B[ib_left]:# A中最大值【大于】B中最大值的情況ifA[ia_right]B[ib_right]:ans1ia_right-1ib_right-1A[ia_right] B[ib_right]即以下情況由于此時B[ib_right]大于A中的任何一個元素A無論如何配對都必輸故仍然維持著田忌賽馬的策略令A[ia_left]和B[ib_right]分組B獲勝。A[ia_right] B[ib_right]即以下情況此時固然可以令A[ia_left]和B[ib_left]、A[ai_right]和B[ib_right]兩兩分組但剩余元素的比較可能會讓A的失利場次增多。以上圖為例子如果選擇A的1和B的1分組A的4和B的4分組那么剩下的A的2只能和B的3分組。A的結(jié)果是平2負1這不是最優(yōu)解。最優(yōu)解仍為A的1和B的4分組剩下就存在A的2和B的1分組A的4和B的3分組。A的結(jié)果是勝2負1這樣才是最優(yōu)解。故仍然應該選擇A[ia_left]和B[ib_right]進行分組此時丟失的分數(shù)可能能夠在A[ia_right]的其他配對中獲取回來。顯然這種情況可以和上一種情況A[ia_right] B[ib_right]合并在一起即# A中最小值【等于】B中最小值的情況ifA[ia_left]B[ib_left]:# A中最大值【小于等于】B中最大值的情況ifA[ia_right]B[ib_right]:# 只有當A中最小值小于B中最大值時A減分ifA[ia_left]B[ib_right]:ans-1ia_left1ib_right-1本題核心邏輯其實就是田忌賽馬在A[ia_left]必定無法勝利的情況下無論是必輸還是可能平局都盡量地讓A[ia_left]和B[ib_right]配對。代碼Python# 題目【貪心】2025A/雙機位A-數(shù)字序列比大小# 分值200# 作者閉著眼睛學數(shù)理化# 算法貪心/雙指針# 代碼看不懂的地方請直接在群上提問nint(input())Alist(map(int,input().split()))Blist(map(int,input().split()))# 分別對A和B數(shù)組進行排序A.sort()B.sort()# 設(shè)置四個指針ia_left0ib_left0ia_rightn-1ib_rightn-1ans0# 進行循環(huán)# 由于每次判斷A和B中的指針必定均移動一位# 故此處只需設(shè)置一個退出循環(huán)條件即可# 此處的循環(huán)不變量為ia_left小于等于ia_right# 即A中的每一個元素都必須遍歷到whileia_leftia_right:# A中最小值【大于】B中最小值的情況ifA[ia_left]B[ib_left]:ans1ia_left1ib_left1# A中最小值【小于】B中最小值的情況elifA[ia_left]B[ib_left]:ans-1ia_left1ib_right-1# A中最小值【等于】B中最小值的情況elifA[ia_left]B[ib_left]:# A中最大值【大于】B中最大值的情況ifA[ia_right]B[ib_right]:ans1ia_right-1ib_right-1# A中最大值【小于等于】B中最大值的情況elifA[ia_right]B[ib_right]:ifA[ia_left]B[ib_right]:ans-1ia_left1ib_right-1print(ans)Javaimportjava.util.Arrays;importjava.util.Scanner;publicclassMain{publicstaticvoidmain(String[]args){ScannerscannernewScanner(System.in);// 輸入nintnscanner.nextInt();int[]Anewint[n];int[]Bnewint[n];// 輸入數(shù)組Afor(inti0;in;i){A[i]scanner.nextInt();}// 輸入數(shù)組Bfor(inti0;in;i){B[i]scanner.nextInt();}// 分別對A和B數(shù)組進行升序排序Arrays.sort(A);Arrays.sort(B);// 初始化四個指針intiaLeft0,ibLeft0;intiaRightn-1,ibRightn-1;intans0;// 循環(huán)直到A數(shù)組被完全遍歷while(iaLeftiaRight){// A中最小值 B中最小值if(A[iaLeft]B[ibLeft]){ans;iaLeft;ibLeft;}// A中最小值 B中最小值elseif(A[iaLeft]B[ibLeft]){ans--;iaLeft;ibRight--;}// A中最小值 B中最小值else{// 比較A中最大值和B中最大值if(A[iaRight]B[ibRight]){ans;iaRight--;ibRight--;}else{if(A[iaLeft]B[ibRight]){ans--;}iaLeft;ibRight--;}}}// 輸出最終得分System.out.println(ans);}}C#include iostream #include vector #include algorithm using namespace std; int main() { int n; cin n; vectorint A(n); vectorint B(n); // 輸入數(shù)組A for (int i 0; i n; i) { cin A[i]; } // 輸入數(shù)組B for (int i 0; i n; i) { cin B[i]; } // 對A和B數(shù)組進行升序排序 sort(A.begin(), A.end()); sort(B.begin(), B.end()); // 初始化四個指針 int iaLeft 0, ibLeft 0; int iaRight n - 1, ibRight n - 1; int ans 0; // 循環(huán)直到A數(shù)組被完全遍歷 while (iaLeft iaRight) { // A中最小值 B中最小值 if (A[iaLeft] B[ibLeft]) { ans; iaLeft; ibLeft; } // A中最小值 B中最小值 else if (A[iaLeft] B[ibLeft]) { ans--; iaLeft; ibRight--; } // A中最小值 B中最小值 else { // 比較A中最大值和B中最大值 if (A[iaRight] B[ibRight]) { ans; iaRight--; ibRight--; } else { if (A[iaLeft] B[ibRight]) { ans--; } iaLeft; ibRight--; } } } // 輸出最終得分 cout ans endl; return 0; }C#includestdio.h#includestdlib.h// 比較函數(shù)用于qsort進行升序排序intcmp(constvoid*a,constvoid*b){return(*(int*)a)-(*(int*)b);}intmain(){intn;scanf(%d,n);// 動態(tài)申請數(shù)組A和Bint*A(int*)malloc(n*sizeof(int));int*B(int*)malloc(n*sizeof(int));// 輸入數(shù)組Afor(inti0;in;i){scanf(%d,A[i]);}// 輸入數(shù)組Bfor(inti0;in;i){scanf(%d,B[i]);}// 對數(shù)組A和B進行升序排序qsort(A,n,sizeof(int),cmp);qsort(B,n,sizeof(int),cmp);// 初始化四個指針intiaLeft0,ibLeft0;intiaRightn-1,ibRightn-1;intans0;// 只要A數(shù)組還有元素未遍歷就繼續(xù)循環(huán)while(iaLeftiaRight){// A中最小值 B中最小值if(A[iaLeft]B[ibLeft]){ans;iaLeft;ibLeft;}// A中最小值 B中最小值elseif(A[iaLeft]B[ibLeft]){ans--;iaLeft;ibRight--;}// A中最小值 B中最小值else{// 比較A中最大值和B中最大值if(A[iaRight]B[ibRight]){ans;iaRight--;ibRight--;}else{if(A[iaLeft]B[ibRight]){ans--;}iaLeft;ibRight--;}}}// 輸出最終得分printf(%d\n,ans);// 釋放動態(tài)分配的內(nèi)存free(A);free(B);return0;}Node JavaScriptconstreadlinerequire(readline);// 創(chuàng)建輸入接口constrlreadline.createInterface({input:process.stdin,output:process.stdout});letinputLines[];rl.on(line,(line){inputLines.push(line.trim());if(inputLines.length2*parseInt(inputLines[0])/parseInt(inputLines[0])1){main();rl.close();}});functionmain(){letnparseInt(inputLines[0]);// 輸入nletAinputLines[1].split( ).map(Number);// 輸入數(shù)組AletBinputLines[2].split( ).map(Number);// 輸入數(shù)組B// 對A和B數(shù)組進行升序排序A.sort((a,b)a-b);B.sort((a,b)a-b);// 初始化四個指針letiaLeft0,ibLeft0;letiaRightn-1,ibRightn-1;letans0;// 循環(huán)直到A數(shù)組被完全遍歷while(iaLeftiaRight){// A中最小值 B中最小值if(A[iaLeft]B[ibLeft]){ans;iaLeft;ibLeft;}// A中最小值 B中最小值elseif(A[iaLeft]B[ibLeft]){ans--;iaLeft;ibRight--;}// A中最小值 B中最小值else{// 比較A中最大值和B中最大值if(A[iaRight]B[ibRight]){ans;iaRight--;ibRight--;}else{if(A[iaLeft]B[ibRight]){ans--;}iaLeft;ibRight--;}}}// 輸出最終得分console.log(ans);}Gopackagemainimport(fmtsort)funcmain(){varnintfmt.Scan(n)A:make([]int,n)B:make([]int,n)// 輸入數(shù)組Afori:0;in;i{fmt.Scan(A[i])}// 輸入數(shù)組Bfori:0;in;i{fmt.Scan(B[i])}// 分別對A和B數(shù)組進行升序排序sort.Ints(A)sort.Ints(B)// 初始化四個指針iaLeft,ibLeft:0,0iaRight,ibRight:n-1,n-1ans:0// 循環(huán)直到A數(shù)組被完全遍歷foriaLeftiaRight{// A中最小值 B中最小值ifA[iaLeft]B[ibLeft]{ansiaLeftibLeft}elseifA[iaLeft]B[ibLeft]{// A中最小值 B中最小值ans--iaLeftibRight--}else{// A中最小值 B中最小值ifA[iaRight]B[ibRight]{// A中最大值 B中最大值ansiaRight--ibRight--}else{// A中最大值 B中最大值ifA[iaLeft]B[ibRight]{ans--}iaLeftibRight--}}}// 輸出最終得分fmt.Println(ans)}時空復雜度時間復雜度O(NlogN)為排序所需的時間復雜度。在while循環(huán)雙指針中兩個列表中的每個元素只會經(jīng)過一次雙指針過程的時間復雜度為O(N)?？臻g復雜度O(1)。僅需四個指針若干常數(shù)變量華為OD算法/大廠面試高頻題算法練習沖刺訓練華子OD算法/大廠面試高頻題算法沖刺訓練目前開始常態(tài)化報名目前已服務1000同學成功上岸課程講師為全網(wǎng)200w粉絲編程博主吳師兄學算法以及小紅書頭部編程博主閉著眼睛學數(shù)理化90天陪伴式學習100直播課時300動畫圖解視頻500LeetCode經(jīng)典題500華為OD真題/大廠真題還有簡歷修改、模擬面試、陪伴小群、資深HR對接將為你解鎖