文章目錄相關(guān)推薦閱讀題目描述與示例題目描述輸入描述輸出描述示例輸入輸出解題思路代碼PythonJavaCCNode JavaScriptGo時(shí)空復(fù)雜度華為OD算法/大廠面試高頻題算法練習(xí)沖刺訓(xùn)練相關(guān)推薦閱讀【華為OD機(jī)考正在更新】2025年雙機(jī)位A卷真題【完全原創(chuàng)題解 | 詳細(xì)考點(diǎn)分類 | 不斷更新題目 | 六種主流語(yǔ)言PyJavaCppCJsGo】【華為OD機(jī)考】2025C2025B2024ED卷真題【完全原創(chuàng)題解 | 詳細(xì)考點(diǎn)分類 | 不斷更新題目】【華為OD筆試】雙機(jī)位A2025C2025B2024ED卷真題機(jī)考套題匯總【真實(shí)反饋不斷更新限時(shí)免費(fèi)】【華為OD筆試】2024ED卷命題規(guī)律解讀【分析500場(chǎng)OD筆試考點(diǎn)總結(jié)】【華為OD流程】性格測(cè)試選項(xiàng)注意事項(xiàng)】題目練習(xí)網(wǎng)址【貪心】雙機(jī)位A-數(shù)字序列比大小題目描述與示例題目描述AB兩個(gè)人玩一個(gè)數(shù)字比大小的游戲在游戲前兩個(gè)人會(huì)拿到相同長(zhǎng)度的兩個(gè)數(shù)字序列兩個(gè)數(shù)字序列不相同的且其中的數(shù)字是隨機(jī)的。AB各自從數(shù)字序列中挑選出一個(gè)數(shù)字進(jìn)行大小比較贏的人得1分輸?shù)娜丝?分相等則各自的分?jǐn)?shù)不變。 用過(guò)的數(shù)字需要丟棄。求A可能贏B的最大分?jǐn)?shù)。輸入描述輸入數(shù)據(jù)的第1個(gè)數(shù)字表示數(shù)字序列的長(zhǎng)度N后面緊跟著兩個(gè)長(zhǎng)度為N的數(shù)字序列。輸出描述A可能贏B的最大分?jǐn)?shù)示例輸入3 4 8 10 3 6 4輸出3解題思路這道題很明顯是一道貪心結(jié)合雙指針的題目。由于平局情況的出現(xiàn)本題難點(diǎn)在于我們?nèi)绾蔚剡x擇策略。很容易想到我們可以采取類似田忌賽馬的策略為了使得A贏的盡可能多每次出現(xiàn)A中元素較小的時(shí)候我們總是選擇這個(gè)較小的元素和B中盡可能大的數(shù)去分組。首先需要將兩個(gè)數(shù)組各自排序方便考慮兩個(gè)數(shù)組里的的最值情況。我們?cè)O(shè)置四個(gè)指針ia_leftia_rightib_leftib_right分別指向A、B數(shù)組中尚未比較過(guò)的元素的最小值和最大值。其初始化為ia_left0ib_left0ia_rightn-1ib_rightn-1如下圖所示在一個(gè)while循環(huán)中比較A和B中尚未比較過(guò)元素的最小值即A[ia_left]和B[ib_left]。若A[ia_left] B[ib_left]。由于選擇B中的其他數(shù)字可能會(huì)導(dǎo)致A[ia_left]無(wú)法獲勝故選擇該組進(jìn)行比較A獲勝。# A中最小值【大于】B中最小值的情況ifA[ia_left]B[ib_left]:ans1ia_left1ib_left1A[ia_left] B[ib_left]。由于此時(shí)A中最小值小于B中的任意一個(gè)元素我們不妨采取田忌賽馬的策略讓A[ia_left]和B[ib_right]進(jìn)行分組B獲勝。# A中最小值【小于】B中最小值的情況ifA[ia_left]B[ib_left]:ans-1ia_left1ib_right-1A[ia_left] B[ib_left]。這是最復(fù)雜的情況我們繼續(xù)考慮A和B中尚未比較過(guò)元素的最大值即A[ia_right]和B[ib_right]情況。若A[ia_right] B[ib_right]即以下情況若此時(shí)令A(yù)[ia_left]和B[ib_right]分組由于A[ia_right]無(wú)論怎么配對(duì)都是必勝但A[ia_left]原本可以平局的配對(duì)現(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]即以下情況由于此時(shí)B[ib_right]大于A中的任何一個(gè)元素A無(wú)論如何配對(duì)都必輸故仍然維持著田忌賽馬的策略令A(yù)[ia_left]和B[ib_right]分組B獲勝。A[ia_right] B[ib_right]即以下情況此時(shí)固然可以令A(yù)[ia_left]和B[ib_left]、A[ai_right]和B[ib_right]兩兩分組但剩余元素的比較可能會(huì)讓A的失利場(chǎng)次增多。以上圖為例子如果選擇A的1和B的1分組A的4和B的4分組那么剩下的A的2只能和B的3分組。A的結(jié)果是平2負(fù)1這不是最優(yōu)解。最優(yōu)解仍為A的1和B的4分組剩下就存在A的2和B的1分組A的4和B的3分組。A的結(jié)果是勝2負(fù)1這樣才是最優(yōu)解。故仍然應(yīng)該選擇A[ia_left]和B[ib_right]進(jìn)行分組此時(shí)丟失的分?jǐn)?shù)可能能夠在A[ia_right]的其他配對(duì)中獲取回來(lái)。顯然這種情況可以和上一種情況A[ia_right] B[ib_right]合并在一起即# A中最小值【等于】B中最小值的情況ifA[ia_left]B[ib_left]:# A中最大值【小于等于】B中最大值的情況ifA[ia_right]B[ib_right]:# 只有當(dāng)A中最小值小于B中最大值時(shí)A減分ifA[ia_left]B[ib_right]:ans-1ia_left1ib_right-1本題核心邏輯其實(shí)就是田忌賽馬在A[ia_left]必定無(wú)法勝利的情況下無(wú)論是必輸還是可能平局都盡量地讓A[ia_left]和B[ib_right]配對(duì)。代碼Python# 題目【貪心】2025A/雙機(jī)位A-數(shù)字序列比大小# 分值200# 作者閉著眼睛學(xué)數(shù)理化# 算法貪心/雙指針# 代碼看不懂的地方請(qǐng)直接在群上提問(wèn)nint(input())Alist(map(int,input().split()))Blist(map(int,input().split()))# 分別對(duì)A和B數(shù)組進(jìn)行排序A.sort()B.sort()# 設(shè)置四個(gè)指針ia_left0ib_left0ia_rightn-1ib_rightn-1ans0# 進(jìn)行循環(huán)# 由于每次判斷A和B中的指針必定均移動(dòng)一位# 故此處只需設(shè)置一個(gè)退出循環(huán)條件即可# 此處的循環(huán)不變量為ia_left小于等于ia_right# 即A中的每一個(gè)元素都必須遍歷到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();}// 分別對(duì)A和B數(shù)組進(jìn)行升序排序Arrays.sort(A);Arrays.sort(B);// 初始化四個(gè)指針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]; } // 對(duì)A和B數(shù)組進(jìn)行升序排序 sort(A.begin(), A.end()); sort(B.begin(), B.end()); // 初始化四個(gè)指針 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進(jìn)行升序排序intcmp(constvoid*a,constvoid*b){return(*(int*)a)-(*(int*)b);}intmain(){intn;scanf(%d,n);// 動(dòng)態(tài)申請(qǐng)數(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]);}// 對(duì)數(shù)組A和B進(jìn)行升序排序qsort(A,n,sizeof(int),cmp);qsort(B,n,sizeof(int),cmp);// 初始化四個(gè)指針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);// 釋放動(dòng)態(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// 對(duì)A和B數(shù)組進(jìn)行升序排序A.sort((a,b)a-b);B.sort((a,b)a-b);// 初始化四個(gè)指針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])}// 分別對(duì)A和B數(shù)組進(jìn)行升序排序sort.Ints(A)sort.Ints(B)// 初始化四個(gè)指針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)}時(shí)空復(fù)雜度時(shí)間復(fù)雜度O(NlogN)為排序所需的時(shí)間復(fù)雜度。在while循環(huán)雙指針中兩個(gè)列表中的每個(gè)元素只會(huì)經(jīng)過(guò)一次雙指針過(guò)程的時(shí)間復(fù)雜度為O(N)?？臻g復(fù)雜度O(1)。僅需四個(gè)指針若干常數(shù)變量華為OD算法/大廠面試高頻題算法練習(xí)沖刺訓(xùn)練華子OD算法/大廠面試高頻題算法沖刺訓(xùn)練目前開始常態(tài)化報(bào)名目前已服務(wù)1000同學(xué)成功上岸課程講師為全網(wǎng)200w粉絲編程博主吳師兄學(xué)算法以及小紅書頭部編程博主閉著眼睛學(xué)數(shù)理化90天陪伴式學(xué)習(xí)100直播課時(shí)300動(dòng)畫圖解視頻500LeetCode經(jīng)典題500華為OD真題/大廠真題還有簡(jiǎn)歷修改、模擬面試、陪伴小群、資深HR對(duì)接將為你解鎖