快捷導(dǎo)航

C語(yǔ)言找出數(shù)組中的特定元素的算法解析

更新時(shí)間：2016年03月15日 17:44:04 作者：wuzhekai1985

這篇文章主要介紹了C語(yǔ)言中找出數(shù)組中特定元素的算法解析,包括找出數(shù)組中兩個(gè)只出現(xiàn)一次的數(shù)字的方法,需要的朋友可以參考下

     問(wèn)題描述：一個(gè)int數(shù)組，里面數(shù)據(jù)無(wú)任何限制，要求求出所有這樣的數(shù)a[i]，其左邊的數(shù)都小于等于它，右邊的數(shù)都大于等于它。能否只用一個(gè)額外數(shù)組和少量其它空間實(shí)現(xiàn)。
      思路：如果能用兩個(gè)輔助數(shù)組，那么相對(duì)來(lái)說(shuō)簡(jiǎn)單一點(diǎn)，可定義數(shù)組Min和數(shù)組Max，其中Min[i]表示自a[i]之后的最小值（包括a[i]），Max[i]表示自a[i]之前元素的最大值。有了這兩個(gè)輔助數(shù)組后，對(duì)于a[i]，如果它大于Max[i-1]并且小于Min[i+1]，那么就符合要求。
      但是題目要求是只用一個(gè)額外數(shù)組，其實(shí)Max數(shù)組可以省去，完全可以邊判斷邊計(jì)算，這是因?yàn)镸ax[i]是自左往右計(jì)算的，而判斷時(shí)也是自左往右，兩個(gè)過(guò)程正好可以合起來(lái)。只需用一個(gè)變量Max保存一下當(dāng)前的最大值即可。下面給出兩種方法的代碼實(shí)現(xiàn)。
      參考代碼：

//函數(shù)功能 ： 找元素 
//函數(shù)參數(shù) ： pArray指向數(shù)組，len為數(shù)組的元素個(gè)數(shù) 
//返回值 ： 無(wú) 
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++)    //計(jì)算自i往前最大值的輔助數(shù)組 
    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--) //計(jì)算自i開始最小值的輔助數(shù)組 
    pMin[i] = (pMin[i+1] <= pArray[i])? pMin[i+1]: pArray[i]; 
 
  if(pArray[0] <= pMin[0])   //檢查第1個(gè)元素是否滿足條件 
    cout<<pArray[0]<<' '; 
  for(i = 1; i < len - 1; i++) 
  { 
    if(pArray[i] >= pMax[i-1] && pArray[i] <=pMin[i+1]) //滿足這個(gè)關(guān)系式的元素符合要求 
      cout<<pArray[i]<<' '; 
  } 
  if(pArray[len-1] >= pMax[len-1]) //檢查第len個(gè)元素是否滿足條件 
    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--) //計(jì)算自i開始最小值的輔助數(shù)組 
    pMin[i] = (pMin[i+1] <= pArray[i])? pMin[i+1]: pArray[i]; 
 
  if(pArray[0] <= pMin[0])   //檢查第1個(gè)元素是否滿足條件 
    cout<<pArray[0]<<' '; 
 
  for(i = 1; i < len - 1; i++) 
  { 
    if(pArray[i] >= Max && pArray[i] <=pMin[i+1]) //滿足這個(gè)關(guān)系式的元素符合要求 
      cout<<pArray[i]<<' '; 
    Max = (Max < pArray[i])? pArray[i]: Max; //更新當(dāng)前最大值 
  } 
  if(pArray[len-1] >= Max) //檢查第len個(gè)元素是否滿足條件 
    cout<<pArray[i]; 
  cout<<endl; 
 
  delete [] pMin; 
  pMin = NULL; 
}

找出數(shù)組中兩個(gè)只出現(xiàn)一次的數(shù)字（數(shù)組）
問(wèn)題描述：一個(gè)整型數(shù)組里除了兩個(gè)數(shù)字之外，其他的數(shù)字都出現(xiàn)了兩次。請(qǐng)寫程序找出這兩個(gè)只出現(xiàn)一次的數(shù)字。要求時(shí)間復(fù)雜度是O(n)，空間復(fù)雜度是O(1)。
思路：如果只有一個(gè)數(shù)字只出現(xiàn)一次，而其他都出現(xiàn)兩次，則直接將所有數(shù)字做一次異或運(yùn)算即可，因?yàn)橄嗟鹊臄?shù)字異或一下結(jié)果為0。如果有兩個(gè)數(shù)字只出現(xiàn)一次，而其他數(shù)字出現(xiàn)了兩次。該怎么辦呢？《編程之美》一書提供了一種方法，即先將所有數(shù)字做一次異或運(yùn)算，得到一個(gè)數(shù)字，然后以該數(shù)字的某非0位作為過(guò)濾位，將數(shù)組分成兩個(gè)部分，此時(shí)只出現(xiàn)一次的數(shù)字會(huì)被分到不同的部分?，F(xiàn)在問(wèn)題就轉(zhuǎn)為只出現(xiàn)一次的情況，對(duì)每部分分別做異或運(yùn)算即可。
參考代碼：

//函數(shù)功能 ： 找出數(shù)組中兩個(gè)只出現(xiàn)一次的數(shù)字 
//函數(shù)參數(shù) ： arr為源數(shù)組，len為數(shù)組元素個(gè)數(shù)，result用來(lái)存放結(jié)果  
//返回值 ：  無(wú) 
void FindIsolateTwo(int *arr, int len, int *result) 
{ 
  int i, all = 0, flag = 1; 
 
  for(i = 0; i < len ; i++) //所有數(shù)異或 
    all ^= arr[i]; 
 
  while(!(all&flag)) //尋找過(guò)濾位 
    flag <<= 1; 
 
  result[0] = result[1] = 0; 
  for(i = 0; i < len; i++) //利用過(guò)濾位區(qū)分 
  { 
    if(flag&arr[i]) 
      result[0] ^= arr[i]; 
    else 
      result[1] ^= arr[i]; 
  } 
}

您可能感興趣的文章: