C說話找出數組中的特定元素的算法解析

C說話找出數組中的特定元素的算法解析。本站提示廣大學習愛好者：（C說話找出數組中的特定元素的算法解析）文章只能為提供參考，不一定能成為您想要的結果。以下是C說話找出數組中的特定元素的算法解析正文

     成績描寫：一個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]; 
  } 
}