問題描述：一個int數組，里面數據無任何限制，要求求出所有這樣的數a[i]，其左邊的數都小于等于它，右邊的數都大于等于它。能否只用一個額外數組和少量其它空間實現。
思路：如果能用兩個輔助數組，那么相對來說簡單一點，可定義數組Min和數組Max，其中Min[i]表示自a[i]之后的最小值（包括a[i]），Max[i]表示自a[i]之前元素的最大值。有了這兩個輔助數組后，對于a[i]，如果它大于Max[i-1]并且小于Min[i+1]，那么就符合要求。
但是題目要求是只用一個額外數組，其實Max數組可以省去，完全可以邊判斷邊計算，這是因為Max[i]是自左往右計算的，而判斷時也是自左往右，兩個過程正好可以合起來。只需用一個變量Max保存一下當前的最大值即可。下面給出兩種方法的代碼實現。
參考代碼：
//函數功能 ： 找元素 //函數參數 ： pArray指向數組，len為數組的元素個數 //返回值 ： 無 void FindElements_Solution1(int *pArray, int len) { if(pArray == NULL || len <= 0 ) return ; int *pMin = new int[len]; int *pMax = new int[len]; int i; pMax[0] = pArray[0]; for(i = 1; i < len; i++) //計算自i往前最大值的輔助數組 pMax[i] = (pMax[i-1] >= pArray[i])? pMax[i-1]: pArray[i]; pMin[len-1] = pArray[len-1]; for(i = len - 2; i >= 0; i--) //計算自i開始最小值的輔助數組 pMin[i] = (pMin[i+1] <= pArray[i])? pMin[i+1]: pArray[i]; if(pArray[0] <= pMin[0]) //檢查第1個元素是否滿足條件 cout<<pArray[0]<<' '; for(i = 1; i < len - 1; i++) { if(pArray[i] >= pMax[i-1] && pArray[i] <=pMin[i+1]) //滿足這個關系式的元素符合要求 cout<<pArray[i]<<' '; } if(pArray[len-1] >= pMax[len-1]) //檢查第len個元素是否滿足條件 cout<<pArray[i]; cout<<endl; delete [] pMin; delete [] pMax; pMin = pMax = NULL; } void FindElements_Solution2(int *pArray, int len) { if(pArray == NULL || len <= 0 ) return ; int *pMin = new int[len]; int Max; int i; Max = pArray[0]; pMin[len-1] = pArray[len-1]; for(i = len - 2; i >= 0; i--) //計算自i開始最小值的輔助數組 pMin[i] = (pMin[i+1] <= pArray[i])? pMin[i+1]: pArray[i]; if(pArray[0] <= pMin[0]) //檢查第1個元素是否滿足條件 cout<<pArray[0]<<' '; for(i = 1; i < len - 1; i++) { if(pArray[i] >= Max && pArray[i] <=pMin[i+1]) //滿足這個關系式的元素符合要求 cout<<pArray[i]<<' '; Max = (Max < pArray[i])? pArray[i]: Max; //更新當前最大值 } if(pArray[len-1] >= Max) //檢查第len個元素是否滿足條件 cout<<pArray[i]; cout<<endl; delete [] pMin; pMin = NULL; } 找出數組中兩個只出現一次的數字（數組）
問題描述：一個整型數組里除了兩個數字之外，其他的數字都出現了兩次。請寫程序找出這兩個只出現一次的數字。要求時間復雜度是O(n)，空間復雜度是O(1)。
思路：如果只有一個數字只出現一次，而其他都出現兩次，則直接將所有數字做一次異或運算即可，因為相等的數字異或一下結果為0。如果有兩個數字只出現一次，而其他數字出現了兩次。該怎么辦呢？《編程之美》一書提供了一種方法，即先將所有數字做一次異或運算，得到一個數字，然后以該數字的某非0位作為過濾位，將數組分成兩個部分，此時只出現一次的數字會被分到不同的部分。現在問題就轉為只出現一次的情況，對每部分分別做異或運算即可。
參考代碼：
//函數功能 ： 找出數組中兩個只出現一次的數字 //函數參數 ： arr為源數組，len為數組元素個數，result用來存放結果 //返回值 ： 無 void FindIsolateTwo(int *arr, int len, int *result) { int i, all = 0, flag = 1; for(i = 0; i < len ; i++) //所有數異或 all ^= arr[i]; while(!(all&flag)) //尋找過濾位 flag <<= 1; result[0] = result[1] = 0; for(i = 0; i < len; i++) //利用過濾位區分 { if(flag&arr[i]) result[0] ^= arr[i]; else result[1] ^= arr[i]; } } 新聞熱點
疑難解答
圖片精選
