程序員面試題精選100題(29)-調整數組順序使奇數位于偶數前面[算法]

時間:2019-09-22 編輯:范文亭
題目:輸入一個整數數組,調整數組中數字的順序,使得所有奇數位于數組的前半部分,所有偶數位于數組的后半部分。要求時間復雜度為O(n)。
分析:如果不考慮時間復雜度,最簡單的思路應該是從頭掃描這個數組,每碰到一個偶數時,拿出這個數字,并把位于這個數字后面的所有數字往前挪動一位。挪完之后在數組的末尾有一個空位,這時把該偶數放入這個空位。由于碰到一個偶數,需要移動O(n)個數字,因此總的時間復雜度是O(n)。
要求的是把奇數放在數組的前半部分,偶數放在數組的后半部分,因此所有的奇數應該位于偶數的前面。也就是說我們在掃描這個數組的時候,如果發現有偶數出現在奇數的前面,我們可以交換他們的順序,交換之后就符合要求了。
因此我們可以維護兩個指針,第一個指針初始化為數組的第一個數字,它只向后移動;第二個指針初始化為數組的最后一個數字,它只向前移動。在兩個指針相遇之前,第一個指針總是位于第二個指針的前面。如果第一個指針指向的數字是偶數而第二個指針指向的數字是奇數,我們就交換這兩個數字。
基于這個思路,我們可以寫出如下的代碼:
void Reorder(int *pData, unsigned int length, bool (*func)(int));
bool isEven(int n);

/////////////////////////////////////////////////////////////////////////
// Devide an array of integers into two parts, odd in the first part,
// and even in the second part
// Input: pData  - an array of integers
//        length - the length of array
/////////////////////////////////////////////////////////////////////////
void ReorderOddEven(int *pData, unsigned int length)
{
      if(pData == NULL || length == 0)
            return;

      Reorder(pData, length, isEven);
}

/////////////////////////////////////////////////////////////////////////
// Devide an array of integers into two parts, the intergers which
// satisfy func in the first part, otherwise in the second part
// Input: pData  - an array of integers
//        length - the length of array
//        func   - a function
/////////////////////////////////////////////////////////////////////////
void Reorder(int *pData, unsigned int length, bool (*func)(int))
{
      if(pData == NULL || length == 0)
            return;

      int *pBegin = pData;
      int *pEnd = pData + length - 1;

      while(pBegin < pEnd)
      {
            // if *pBegin does not satisfy func, move forward
            if(!func(*pBegin))
            {
                  pBegin ++;
                  continue;
            }

            // if *pEnd does not satisfy func, move backward
            if(func(*pEnd))
            {
                  pEnd --;
                  continue;
            }

            // if *pBegin satisfy func while *pEnd does not,
            // swap these integers
            int temp = *pBegin;
            *pBegin = *pEnd;
            *pEnd = temp;
      }
}

/////////////////////////////////////////////////////////////////////////
// Determine whether an integer is even or not
// Input: an integer
// otherwise return false
/////////////////////////////////////////////////////////////////////////
bool isEven(int n)
{
      return (n & 1) == 0;
}
討論:
上面的代碼有三點值得提出來和大家討論:
1.函數isEven判斷一個數字是不是偶數并沒有用%運算符而是用&。理由是通常情況下位運算符比%要快一些;
2.這道題有很多變種。這里要求是把奇數放在偶數的前面,如果把要求改成:把負數放在非負數的前面等,思路都是都一樣的。
3.在函數Reorder中,用函數指針func指向的函數來判斷一個數字是不是符合給定的條件,而不是用在代碼直接判斷(hard code)。這樣的好處是把調整順序的算法和調整的標準分開了(即解耦,decouple)。當調整的標準改變時,Reorder的代碼不需要修改,只需要提供一個新的確定調整標準的函數即可,提高了代碼的可維護性。例如要求把負數放在非負數的前面,我們不需要修改Reorder的代碼,只需添加一個函數來判斷整數是不是非負數。這樣的思路在很多庫中都有廣泛的應用,比如在STL的很多算法函數中都有一個仿函數(functor)的參數(當然仿函數不是函數指針,但其思想是一樣的)。如果在面試中能夠想到這一層,無疑能給面試官留下很好的印象。
本文已影響
相關文章
大亨pk10计划苹果版