網(wǎng)站建設實錄,免費空間忘記密碼解決方法,公眾號圖片wordpress,網(wǎng)絡會議系統(tǒng)方案輸入#xff1a; 非空整數(shù)數(shù)組 nums#xff08;可能包含重復元素#xff09;。 要求#xff1a; 返回數(shù)組中第三大的不同數(shù)字#xff1b;如果不存在第三大的不同數(shù)字#xff0c;則返回數(shù)組中的最大值。 輸出#xff1a; 整數(shù)#xff08;第三大或最大值#xff09;。思…輸入非空整數(shù)數(shù)組nums可能包含重復元素。要求返回數(shù)組中第三大的不同數(shù)字如果不存在第三大的不同數(shù)字則返回數(shù)組中的最大值。輸出整數(shù)第三大或最大值。思路題眼是“第三大”指的是不同數(shù)字的第三大所以必須去重。用一次遍歷維護三個變量max1當前最大值max2當前第二大不同值max3當前第三大不同值初始化都為LLONG_MIN避免數(shù)組里有INT_MIN時沖突。遍歷每個元素v時先去重如果v等于max1/max2/max3直接跳過。然后把v放進這三個槽位里類似插入排序的三格版v max1整體后移max3max2, max2max1, max1v否則如果v max2max3max2, max2v否則如果v max3max3v遍歷結束如果max3還是沒被填過仍為LLONG_MIN說明不足三個不同數(shù)返回max1否則返回max3復雜度時間復雜度O(N)空間復雜度O(1)classSolution{public:intthirdMax(vectorintnums){longlongmax1LLONG_MIN,max2LLONG_MIN,max3LLONG_MIN;for(intx:nums){longlongvx;// 去重只統(tǒng)計“不同數(shù)字”的排名if(vmax1||vmax2||vmax3)continue;if(vmax1){max3max2;max2max1;max1v;}elseif(vmax2){max3max2;max2v;}elseif(vmax3){max3v;}}return(max3LLONG_MIN)?(int)max1:(int)max3;}};