生活随笔
收集整理的這篇文章主要介紹了
数组面试题
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
http://blog.csdn.net/hackbuteer1/article/details/8035261
1、快速找出一個數(shù)組中的最大數(shù)、第二大數(shù)。
???? 思路：如果當(dāng)前元素大于最大數(shù) max，則讓第二大數(shù)等于原來的最大數(shù) max，再把當(dāng)前元素的值賦給 max。如果當(dāng)前的元素大于等于第二大數(shù)secondMax的值而小于最大數(shù)max的值，則要把當(dāng)前元素的值賦給 secondMax。
[cpp]?view plaincopy
void?GetSecondMaxNumber(int?*arr?,?int?n)?? {?? ????int?i?,?max?,?second_max;?? ????max?=?arr[0];?? ????second_max?=?0x80000000;?? ????for(i?=?1?;?i?<?n?;?++i)?? ????{?? ????????if(arr[i]?>?max)?? ????????{?? ????????????second_max?=?max;?? ????????????max?=?arr[i];?? ????????}?? ????????else?? ????????{?? ????????????if(arr[i]?>?second_max)?? ????????????????second_max?=?arr[i];?? ????????}?? ????}?? ????cout<<max<<"??"<<second_max<<endl;?? }??
2、試著用最小的比較次數(shù)去尋找數(shù)組中的最大值和最小值。
解法一：
掃描一次數(shù)組找出最大值；再掃描一次數(shù)組找出最小值。
比較次數(shù)2N-2
解法二：
將數(shù)組中相鄰的兩個數(shù)分在一組， 每次比較兩個相鄰的數(shù)，將較大值交換至這兩個數(shù)的左邊，較小值放于右邊。
對大者組掃描一次找出最大值，對小者組掃描一次找出最小值。
比較1.5N-2次，但需要改變數(shù)組結(jié)構(gòu)
?
解法三：
每次比較相鄰兩個數(shù)，較大者與MAX比較，較小者與MIN比較，找出最大值和最小值。
方法如下：先將一對元素互相進行比較，然后把最小值跟當(dāng)前最小值進行比較，把最大值跟當(dāng)前最大值進行比較。因此每兩個元素需要3次比較。如果n為奇數(shù)，那么比較的次數(shù)是3*(n/2)次比較。如果n為偶數(shù)，那么比較的次數(shù)是3n/2-2次比較。因此，不管是n是奇數(shù)還是偶數(shù)，比較的次數(shù)至多是3*(n/2)，具體的代碼如下：
[cpp]?view plaincopy
void?GetMaxAndMin(int?*arr?,?int?n?,?int?&max?,?int?&min)?? {?? ????int?i?=?0?;?? ????if(n?&?1)??????? ????{?? ????????max?=?min?=?arr[i++];?? ????}?? ????else?? ????{?? ????????if(arr[0]?>?arr[1])?? ????????{?? ????????????max?=?arr[0];?? ????????????min?=?arr[1];?? ????????}?? ????????else?? ????????{?? ????????????max?=?arr[1];?? ????????????min?=?arr[0];?? ????????}?? ????????i?+=?2;?? ????}?? ?????? ????for(?;?i?<?n?;?i?+=?2)?? ????{?? ????????if(arr[i]?>?arr[i+1])?? ????????{?? ????????????if(arr[i]?>?max)?? ????????????????max?=?arr[i];?? ????????????if(arr[i+1]?<?min)?? ????????????????min?=?arr[i+1];?? ????????}?? ????????else?? ????????{?? ????????????if(arr[i+1]?>?max)?? ????????????????max?=?arr[i+1];?? ????????????if(arr[i]?<?min)?? ????????????????min?=?arr[i];?? ????????}?? ????}?? }??
3、重排問題
給定含有n個元素的整型數(shù)組a，其中包括0元素和非0元素，對數(shù)組進行排序，要求：
1、排序后所有0元素在前，所有非零元素在后，且非零元素排序前后相對位置不變
2、不能使用額外存儲空間
例子如下
輸入 0、3、0、2、1、0、0
輸出 0、0、0、0、3、2、1
分析
此排序非傳統(tǒng)意義上的排序，因為它要求排序前后非0元素的相對位置不變，或許叫做整理會更恰當(dāng)一些。我們可以從后向前遍歷整個數(shù)組，遇到某個位置i上的元素是非0元素時，如果arr[k]為0，則將arr[i]賦值給arr[k]，arr[i]賦值為0。實際上i是非0元素的下標(biāo)，而k是0元素的下標(biāo)。
[cpp]?view plaincopy
void?Arrange(int?*arr?,?int?n)?? {?? ????int?i?,?k?=?n-1;?? ????for(i?=?n-1?;?i?>=0?;?--i)?? ????{?? ????????if(arr[i]?!=?0)?? ????????{?? ????????????if(arr[k]?==?0)?? ????????????{?? ????????????????arr[k]?=?arr[i];?? ????????????????arr[i]?=?0;?? ????????????}?? ????????????--k;?? ????????}?? ????}?? }??
4、找出絕對值最小的元素
給定一個有序整數(shù)序列（非遞減序），可能包含負(fù)數(shù)，找出其中絕對值最小的元素，比如給定序列 -5、-3、-1、2、8 則返回1。
分析：由于給定序列是有序的，而這又是搜索問題，所以首先想到二分搜索法，只不過這個二分法比普通的二分法稍微麻煩點，可以分為下面幾種情況
??? 如果給定的序列中所有的數(shù)都是正數(shù)，那么數(shù)組的第一個元素即是結(jié)果。
??? 如果給定的序列中所有的數(shù)都是負(fù)數(shù)，那么數(shù)組的最后一個元素即是結(jié)果。
??? 如果給定的序列中既有正數(shù)又有負(fù)數(shù)，那么絕對值的最小值一定出現(xiàn)在正數(shù)和負(fù)數(shù)的分界處。
為什么？因為對于負(fù)數(shù)序列來說，右側(cè)的數(shù)字比左側(cè)的數(shù)字絕對值小，如上面的-5、-3、-1，而對于整整數(shù)來說，左邊的數(shù)字絕對值小，比如上面的2、8，將這個思想用于二分搜索，可先判斷中間元素和兩側(cè)元素的符號，然后根據(jù)符號決定搜索區(qū)間，逐步縮小搜索區(qū)間，直到只剩下兩個元素。
單獨設(shè)置一個函數(shù)用來判斷兩個整數(shù)的符號是否相同
[cpp]?view plaincopy
bool?SameSign(int?m?,?int?n)?? {?? ????if((m>>31)?==?(n>>31))?? ????????return?true;?? ????else?? ????????return?false;?? }?? ?? ?? int?MiniNumAbsoluteValue(int?*arr?,?int?n)?? {?? ????if(n?==?1)?? ????????return?arr[0];?? ????if(?SameSign(arr[0]?,?arr[n-1])?)?? ????????return?arr[0]?>=?0???arr[0]?:?abs(arr[n-1]);?? ?? ?????? ????int?mid?,?low?=?0?,?high?=?n?-?1;?? ????while(low?<?high)?? ????{?? ????????if(low?+?1?==?high)?? ????????????return?abs(arr[low])?<?abs(arr[high])???abs(arr[low])?:?abs(arr[high]);?? ????????mid?=?(low?+?high)>>1;?? ????????if(?SameSign(arr[low]?,?arr[mid])?)?? ????????{?? ????????????low?=?mid?;??????? ????????????continue;?? ????????}?? ????????if(?SameSign(arr[high]?,?arr[mid])?)?? ????????{?? ????????????high?=?mid;?? ????????????continue;?? ????????}?? ????}?? ????return?abs(arr[low]);?? }??
5、一道經(jīng)典的額遞歸題目
函數(shù) int func(int i ,int N);
其中i <= N，功能輸出i遞增到N再遞減到i的整數(shù)，每行輸出一個數(shù)。比如func(1,5)就是
1
2
3
4
5
4
3
2
1
要求：
1、只能有1個語句，即一個分號
2、不能使用do while until goto for if關(guān)鍵字，不能使用?:和逗號運算符
3、唯一能使用的庫函數(shù)為printf?
[cpp]?view plaincopy
<span?style="font-family:Verdana;font-size:14px;">int?func(int?i?,?int?n)?? {?? ????return?(i==n?&&?printf("%d\n",i))?||?(printf("%d\n",i)?&&?func(i+1,n)?&&?printf("%d\n",i));?? }</span>??
6、從長度為n的數(shù)組（元素互不相同）中任意選擇m個數(shù)的所有組合。
DFS
[cpp]?view plaincopy
? ? ? ?? #include<iostream>?? #include<vector>?? using?namespace?std;?? ?? int?arr[]?=?{1,2,3,4,5,6,7,8,9,10};?? int?len?=?10?,?m?=?3;?? ?? void?dfs(int?num?,?vector<int>&?vec?,?int?curnum?,?int?id)?? {?? ????int?i?;?? ????if(curnum?==?num)?? ????{?? ????????static?int?k?=?1?;?? ????????cout<<k++<<":?";?? ????????for(?i?=?0;?i?<?vec.size()?;?++i)?? ????????????cout<<vec[i]<<"?";?? ????????cout<<endl;?? ????????return;?? ????}?? ?? ????for(?i?=?id;?i?<?len;?++i)?? ????{?? ????????vec.push_back(arr[i]);?? ????????dfs(num?,?vec?,?curnum?+?1?,?i?+?1);?? ????????vec.pop_back();?? ????}?? }?? ?? int?main(void)?? {?? ????vector<int>vec;?? ????dfs(m?,?vec?,?0?,?0);?? ????return?0;?? }??
[cpp]?view plaincopy
int?arr[]?=?{1,2,3,4,5,8,5,8,9,10};?? int?len?=?10?,?m?=?3;?? ?? void?dfs(int?index?,?int?num?,?vector<int>?&vec)?? {?? ????int?i?;?? ????if(index?==?len+1)?? ????????return?;?? ????if(num?==?0)?? ????{?? ????????static?int?k?=?1?;?? ????????cout<<k++<<":?";?? ????????for(?i?=?0;?i?<?vec.size()?;?++i)?? ????????????cout<<vec[i]<<"?";?? ????????cout<<endl;?? ????????return;?? ????}?? ????vec.push_back(arr[index]);?????? ????dfs(index?+?1?,?num?-?1?,?vec);?? ????vec.pop_back();????????????????? ????dfs(index?+?1?,?num?,?vec);?? }?? ?? int?main(void)?? {?? ????vector<int>vec;?? ????dfs(0?,?m?,?vec);?? ????return?0;?? }??
7、從長度為n的數(shù)組（元素有可能相同）中任意選擇m個數(shù)的所有組合。
先對數(shù)組進行排序，然后設(shè)置一個標(biāo)記pre，記錄前一個選擇的數(shù)字，然后進行比較。
[cpp]?view plaincopy
? ? ? ?? #include<iostream>?? #include<vector>?? #include<algorithm>?? using?namespace?std;?? ?? int?arr[]?=?{1,2,3,4,5,8,5,8,9,10};?? int?len?=?10?,?m?=?3;?? ?? void?dfs(int?num?,?vector<int>&?vec?,?int?curnum?,?int?id)?? {?? ????int?i?,?pre?=?-1;?? ????if(curnum?==?num)?? ????{?? ????????static?int?k?=?1?;?? ????????cout<<k++<<":?";?? ????????for(?i?=?0;?i?<?vec.size()?;?++i)?? ????????????cout<<vec[i]<<"?";?? ????????cout<<endl;?? ????????return;?? ????}?? ?? ????for(?i?=?id;?i?<?len;?++i)?? ????{?? ????????if(pre?==?-1?||?arr[i]?>?pre)?? ????????{?? ????????????vec.push_back(arr[i]);?? ????????????dfs(num?,?vec?,?curnum?+?1?,?i?+?1);?? ????????????vec.pop_back();?? ????????????pre?=?arr[i];?? ????????}?? ????}?? }?? ?? int?main(void)?? {?? ????vector<int>vec;?? ????sort(arr?,?arr?+?len?);?? ????dfs(m?,?vec?,?0?,?0);?? ????return?0;?? }??
8、三色旗排序問題
一個字符串Color，其中每個元素值為‘R‘’G’‘B’三者之一，實現(xiàn)把數(shù)組中元素重新排列為紅、綠、藍的順序，所有紅色在前，綠色其后，藍色最后，要如何移動次數(shù)才會最少，編寫這么一個程序。
問題的解法很簡單，您可以自己想像一下在移動旗子，從繩子開頭進行，遇到紅色往前移，遇到綠色留在中間，遇到藍色往后移。
設(shè)有三個指針rindex、gindex、bindex，其中g(shù)index來遍歷這個數(shù)組序列
1、gindex指向G的時候，gindex++，
2、gindex指向R的時候，與rindex交換，而后gindex++，rindex++，
3、gindex指向B的時候，與bindex交換，而后，gindex不動，bindex--。
??? 為什么，第三步，gindex指向B的時候，與bindex交換之后，gindex不動。
??? 因為你最終的目的是為了讓R、G、B成為有序排列，試想，如果第三步，gindex與bindex交換之前，萬一bindex指向的是R，而gindex交換之后，gindex此刻指向的是R了，此時，gindex能動么？不能動啊，指向的是R，還得與rindex交換。
[cpp]?view plaincopy
?? ?? void?mysort(char?*str?,?int?n)?? {?? ????int?rindex?=?0?,?gindex?=?0?,?bindex?=?n?-?1?;?? ????while(gindex?<=?bindex)?? ????{?? ????????if(str[gindex]?==?'G')?? ????????????++gindex;?? ????????else?if(str[gindex]?==?'R')?? ????????{?? ????????????swap(str[gindex]?,?str[rindex]);?? ????????????++rindex?,?++gindex;?? ????????}?? ????????else????????????? ????????{?? ????????????swap(str[gindex]?,?str[bindex]);?? ????????????--bindex;?? ?????????????? ????????}?? ????}?? }??
9、一個整型數(shù)組，含有N個數(shù)，將這N個數(shù)分成連續(xù)的M段，使得這M段每段的和中的最大值最小，輸出最小值。（1<=N<=100000,1<=M<=N,每個數(shù)在1到10000之間）?? POJ? 3273
解題思路：不管分成多少段，每種分法和的最大值都在N個數(shù)的最大值和N個數(shù)的和之間，所求答案也在這之間。
我們可以以此為上下界，二分M段和的最大值進行嘗試。對每次二分的值，將數(shù)組掃描累加。若當(dāng)前和大于二分的這個值，則段數(shù)加一，由此統(tǒng)計出在當(dāng)前值下，N個數(shù)能夠分成的最小段數(shù)。若這個段數(shù)小于或等于M，則向上界變?yōu)閙id-1，并記下當(dāng)前mid的值。否則，下界變?yōu)閙id+1。繼續(xù)二分，直到退出循環(huán)。最后記錄的low值即為答案。
[cpp]?view plaincopy
#include<iostream>?? #include<cstdio>?? using?namespace?std;?? ?? int?m?,?n?,?a[100001];?? ?? int?bsearch(int?low?,?int?high)?? {?? ????int?i?,?mid?,?group?,?sum;?? ????while(low?<=?high)?? ????{?? ????????mid?=?(low?+?high)>>1;?? ????????sum?=?0?,??group?=?1;?? ????????for(i?=?0?;?i?<?n?;?++i)?? ????????{?? ????????????if(sum?+?a[i]?<=?mid)?? ????????????????sum?+=?a[i];?? ????????????else?? ????????????{?? ????????????????group++;?? ????????????????sum?=?a[i];?? ????????????}?? ????????}?? ????????if(group?<=?m)?? ????????????high?=?mid?-?1?;?? ????????else?if(group?>?m)?? ????????????low?=?mid?+?1;?? ????}?? ????return?low;?? }?? ?? int?main(void)?? {?? ????int?i?,?max?,?sum;?? ????while(scanf("%d?%d",&n,&m)!=EOF)?? ????{?? ????????max?=?0x80000000?,?sum?=?0;?? ????????for(i?=?0?;?i?<?n?;?++i)?? ????????{?? ????????????scanf("%d",&a[i]);?? ????????????sum?+=?a[i];?? ????????????if(a[i]?>?max)?? ????????????????max?=?a[i];?? ????????}?? ????????printf("%d\n",bsearch(max,?sum));?? ????}?? ????return?0;?? }??
10、一個int數(shù)組，里面數(shù)據(jù)無任何限制，要求求出所有這樣的數(shù)a[i]，其左邊的數(shù)都小于等于它，右邊的數(shù)都大于等于它。
能否只用一個額外數(shù)組和少量其它空間實現(xiàn)。
分析：最原始的方法是檢查每一個數(shù) array[i] ，看是否左邊的數(shù)都小于等于它，右邊的數(shù)都大于等于它。這樣做的話，要找出所有這樣的數(shù)，時間復(fù)雜度為O(N^2)。
其實可以有更簡單的方法，我們使用額外數(shù)組，比如rightMin[]，來幫我們記錄原始數(shù)組array[i]右邊（包括自己）的最小值。假如原始數(shù)組為： array[] = {7, 10, 2, 6, 19, 22, 32}， 那么rightMin[] = {2, 2, 2, 6, 19, 22, 32}. 也就是說，7右邊的最小值為2, 2右邊的最小值也是2。
有了這樣一個額外數(shù)組，當(dāng)我們從頭開始遍歷原始數(shù)組時，我們保存一個當(dāng)前最大值 max， 如果當(dāng)前最大值剛好等于rightMin[i]， 那么這個最大值一定滿足條件。還是剛才的例子。
第一個值是7，最大值也是7，因為7 不等于 2， 繼續(xù)，
第二個值是10，最大值變成了10，但是10也不等于2，繼續(xù)，
第三個值是2，最大值是10，但是10也不等于2，繼續(xù)，
第四個值是6，最大值是10，但是10不等于6，繼續(xù)，
第五個值是19，最大值變成了19，而且19也等于當(dāng)前rightMin[4] = 19, 所以，滿足條件。如此繼續(xù)下去，后面的幾個都滿足。
[cpp]?view plaincopy
int?arr[100]?,?rightMin[100];?? void?smallLarge(int?*arr?,?int?*rightMin?,?int?n)?? {?? ????int?i?,?leftMax;?? ????rightMin[n?-?1]?=?arr[n?-?1];?? ????for(i?=?n?-?2?;?i?>=?0?;?--i)?? ????{?? ????????if(arr[i]?<?arr[i+1])?? ????????????rightMin[i]?=?arr[i];?? ????????else?? ????????????rightMin[i]?=?rightMin[i?+?1];?? ????}?? ????leftMax?=?0x80000000;?? ????for(i?=?0?;?i?<?n?;?++i)?? ????{?? ????????if(arr[i]?>=?leftMax)?? ????????{?? ????????????leftMax?=?arr[i];?? ????????????if(leftMax?==?rightMin[i])?? ????????????????printf("%d\n",leftMax);?? ????????}?? ????}?? }??
?11、整數(shù)的拆分問題
如，對于正整數(shù)n=6，可以拆分為：
6
5+1
4+2, 4+1+1
3+3, 3+2+1, 3+1+1+1
2+2+2, 2+2+1+1, 2+1+1+1+1
1+1+1+1+1+1+1
現(xiàn)在的問題是，對于給定的正整數(shù)n，程序輸出該整數(shù)的拆分種類數(shù)(HDOJ? 1028)。
DP思路：
n = n1 + n2 + n3 + n4 + .... + nk
狀態(tài)表示：將n劃分為k個數(shù)相加的組合方案數(shù)記為 q(n,k)。（相當(dāng)于將n個蘋果放入k個盤子）
狀態(tài)轉(zhuǎn)移：
(1)若k>n，則盤子數(shù)大于蘋果數(shù)，至少有n-k個空盤子，可以將其拿掉，對組合方案數(shù)無影響。
q(n,k) = q(n,n)
(2)若k<=n，則盤子數(shù)小于等于蘋果數(shù)，則分為兩種情況
1.至少有一個盤子空著：q(n,k) = q(n,k-1)
2.所有盤子都不空：q(n,k) = q(n-k,k)
q(n,k) = q(n,k-1) + q(n-k,k)
方法一：DP非遞歸
[cpp]?view plaincopy
int?main(void)?? {?? ????int?n,i,j,dp[121][121];?? ????for(i?=?1?;?i?<?121?;?++i)?? ????{?? ????????for(j?=?1?;?j?<?121?;?++j)?? ????????{?? ????????????if(i?==?1?||??j?==?1)?? ????????????????dp[i][j]?=?1;?? ????????????else?if(i?>?j)?? ????????????????dp[i][j]?=?dp[i][j-1]?+?dp[i-j][j];?? ????????????else?if(i?==?j)?? ????????????????dp[i][j]?=?dp[i][j-1]?+?1;?? ????????????else?? ????????????????dp[i][j]?=?dp[i][i];?? ????????}?? ????}?? ?? ????while(scanf("%d",&n)!=EOF)?? ????{?? ????????cout<<dp[n][n]<<endl;?? ????}?? ????return?0;?? }??
方法二：遞歸思路
[cpp]?view plaincopy
int?q(int?n?,?int?m)?? {?? ????if(n?<?1?||?m?<?1)?? ????????return?0;?? ????if(n?==?1?||?m?==?1)?? ????????return?1;?? ????if(n?<?m)?? ????????return?q(n?,?n);?? ????if(n?==?m)?? ????????return?q(n?,?m?-?1)?+?1;?? ????return?q(n?,?m?-?1)?+?q(n?-?m?,?m);?? }?? ?? int?main(void)?? {?? ????int?n;?? ????while(scanf("%d",&n)!=EOF)?? ????{?? ????????cout<<q(n,n)<<endl;?? ????}?? ????return?0;?? }??
12、整數(shù)的拆分問題
接著上一題，輸出整數(shù)的所有劃分方案
[cpp]?view plaincopy
void?dfs(int?sum?,?vector<int>&?vec?,?int?curnum?,?int?id)?? {?? ????int?i;?? ????if(curnum?==?sum)?? ????{?? ????????static?int?inum?=?1?;?? ????????cout<<"方案?"<<inum++<<":?";?? ????????for(i?=?0;?i?<?vec.size()?;?++i)?? ????????????cout<<vec[i]<<"?";?? ????????cout<<endl;?? ????????return;?? ????}?? ?? ????for(i?=?id?;?i?<=?sum;?++i)?? ????{?? ????????if(curnum?+?i?<=?sum)?? ????????{?? ????????????vec.push_back(i);?? ????????????dfs(sum?,?vec?,?curnum?+?i?,?i);?? ????????????vec.pop_back();?? ????????}?? ????????else?? ????????????break;?? ????}?? }?? ?? void?main()?? {?? ????vector<int>?vec;?? ????dfs(10?,?vec?,?0?,?1);?? }??
13、在數(shù)組中尋找和為給定值的組合
思路：
代碼
14、字符串移動
字符串為*號和26個字母、阿拉伯?dāng)?shù)字的任意組合，把*號都移動到最左側(cè)，把其他字母和數(shù)字都移到最右側(cè)并保持相對順序不變，返回字符*的個數(shù)，要求時間和空間復(fù)雜度最小。
第一種方法：跟上面的重排問題是一樣的
[cpp]?view plaincopy
int?MoveStar(char?*str?,?int?n)?? {?? ????int?i?,?j?=?n-1;?? ????for(i?=?n?-?1?;?i?>=?0?;?--i)?? ????{?? ????????if(str[i]?!=?'*')?? ????????{?? ????????????if(str[j]?==?'*')?? ????????????{?? ????????????????str[j]?=?str[i];?? ????????????????str[i]?=?'*';?? ????????????}?? ????????????--j;?? ????????}?? ????}?? ????return?j+1;?? }??
第二種方法：
[cpp]?view plaincopy
int?MoveStar(char?*str?,?int?n)?? {?? ????int?i?,?count?=?0;?? ????for(i?=?n?-?1?;?i?>=?0?;?--i)?? ????{?? ????????if(str[i]?==?'*')?? ????????????++count;?? ????????else?if(count?>?0)?????? ????????????str[i?+?count]?=?str[i];?? ????}?? ????for(i?=?0?;?i?<?count?;?++i)?? ????????str[i]?=?'*';?? ????return?count;?? }??
時間復(fù)雜度O(N)，空間復(fù)雜度O(1)
15、求數(shù)組中兩個元素差的最大值
后面的元素減去前面的元素（你可以認(rèn)為你在炒股票，買入價格和賣出價格就是你的盈利），要求：O(N)時間復(fù)雜度，O(1)空間復(fù)雜度?
思路：首先從包含兩個元素的數(shù)組開始考慮問題，當(dāng)這個包含兩個元素的問題解決了，那么加一個新的元素會造成什么影響？要改變哪些值？每次都添加一個元素，每次都將這些可能的改變考慮進來，這樣就能做到遍歷整個數(shù)組的時候，問題就解決了。
[cpp]?view plaincopy
?? int?max_difference(int?*arr?,?int?n)?? {?? ????if(arr?==?NULL?||?n?<?2)?????? ????????return?0;?? ????int?min?=?arr[0];?? ????int?maxDiff?=?arr[1]?-?arr[0];?? ????for(int?i?=?2?;?i?<?n?;?++i)?? ????{?? ????????if(arr[i-1]?<?min)?? ????????????min?=?arr[i-1];?? ????????if(arr[i]?-?min?>?maxDiff)?? ????????????maxDiff?=?arr[i]?-?min;?? ????}?? ????return?maxDiff;?? }??
16、求數(shù)組中兩個元素差的最大值
前面的元素減去后面的元素，要求：O(N)時間復(fù)雜度，O(1)空間復(fù)雜度
思路：跟上一題的思路很相近
[cpp]?view plaincopy
?? int?max_difference(int?*arr?,?int?n)?? {?? ????if(arr?==?NULL?||?n?<?2)?????? ????????return?0;?? ????int?max?=?arr[0];?? ????int?maxDiff?=?arr[0]?-?arr[1];?? ????for(int?i?=?2?;?i?<?n?;?++i)?? ????{?? ????????if(arr[i-1]?>?max)?? ????????????max?=?arr[i-1];?? ????????if(max?-?arr[i]?>?maxDiff)?? ????????????maxDiff?=?max?-?arr[i];?? ????}?? ????return?maxDiff;?? }??
總結(jié)
以上是生活随笔為你收集整理的数组面试题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
