關于數組的求和

數組是最基本的數據結構，關于數組的面試題也屢見不鮮，本文羅列了一些常見的面試題，僅供參考，如果您有更好的題目或者想法，歡迎留言討論。目前有以下18道題目，如果有好的題目，隨時更新。

數組求和

求數組的最大值和最小值

求數組的最大值和次大值

求數組中出現次數超過一半的元素

求數組中元素的最短距離

找出絕對值最小的元素

數組求和

給定一個含有n個元素的整型數組a，求a中所有元素的和?？赡苣鷷X得很簡單，是的，的確簡單，但是為什么還要說呢，原因有二，第一，這道題要求用遞歸法，只用一行代碼。第二，這是我人生中第一次面試時候遇到的題，意義特殊。

分析

簡單說一下，兩種情況

1. 如果數組元素個數為0，那么和為0。

2. 如果數組元素個數為n，那么先求出前n - 1個元素之和，再加上a[n - 1]即可

代碼

// 數組求和int sum(int*a, int n){     return n == 0 ? 0 : sum(a, n -1) + a[n -1];}

求數組的最大值和最小值

給定一個含有n個元素的整型數組a，找出其中的最大值和最小值

分析

常規(guī)的做法是遍歷一次，分別求出最大值和最小值，但我這里要說的是分治法(Divide and couquer)，將數組分成左右兩部分，先求出左半部份的最大值和最小值，再求出右半部份的最大值和最小值，然后綜合起來求總體的最大值及最小值。這是個遞歸過程，對于劃分后的左右兩部分，同樣重復這個過程，直到劃分區(qū)間內只剩一個元素或者兩個元素。

代碼

// 求數組的最大值和最小值，返回值在maxValue和minValuevoid MaxandMin(int *a, int l, int r, int& maxValue, int& minValue){    if(l == r) // l與r之間只有一個元素    {        maxValue = a[l] ;        minValue = a[l] ;        return ;    }
    if(l + 1 == r) // l與r之間只有兩個元素    {        if(a[l] >= a[r])        {            maxValue = a[l] ;            minValue = a[r] ;        }        else        {            maxValue = a[r] ;            minValue = a[l] ;        }        return ;    }
    int m = (l + r) / 2 ; // 求中點
    int lmax ; // 左半部份最大值    int lmin ; // 左半部份最小值    MaxandMin(a, l, m, lmax, lmin) ; // 遞歸計算左半部份
    int rmax ; // 右半部份最大值    int rmin ; // 右半部份最小值    MaxandMin(a, m + 1, r, rmax, rmin) ; // 遞歸計算右半部份
    maxValue = max(lmax, rmax) ; // 總的最大值    minValue = min(lmin, rmin) ; // 總的最小值}

求數組的最大值和次大值

給定一個含有n個元素的整型數組，求其最大值和次大值

分析

思想和上一題類似，同樣是用分治法，先求出左邊的最大值leftmax和次大值leftsecond，再求出右邊的最大值rightmax和次大值rightsecond，然后合并，如何合并呢？分情況考慮

1 如果leftmax > rightmax，那么可以肯定leftmax是最大值，但次大值不一定是rightmax，但肯定不是rightsecond，只需將leftsecond與rightmax做一次比較即可。

2 如果rightmax > leftmax，那么可以肯定rightmax是最大值，但次大值不一定是leftmax，但肯定不是leftsecond，所以只需將leftmax與rightsecond做一次比較即可。

注意

這種方法無法處理最大元素有多個的情況，比如3,5,7,7將返回7，7而不是7,5。感謝網友從無到有靠誰人指出。

代碼

// 找出數組的最大值和次大值，a是待查找的數組，left和right是查找區(qū)間，max和second存放結果void MaxandMin(int a[], int left, int right, int&max, int&second){    if(left == right)    {        max = a[left] ;        second =  INT_MIN;    }    elseif(left +1== right)    {        max = a[left] > a[right] ? a[left] : a[right] ;        second = a[left] < a[right] ? a[left] : a[right] ;    }    else    {        int mid = left + (right - left) /2 ;
        int leftmax ;        int leftsecond ;        MaxandMin(a, left, mid, leftmax, leftsecond) ;
        int rightmax ;        int rightsecond ;        MaxandMin(a, mid +1, right, rightmax, rightsecond) ;
        if (leftmax > rightmax)        {            max = leftmax ;            second = leftsecond > rightmax ? leftsecond : rightmax ;        }        else        {            max = rightmax ;            second = leftmax < rightsecond ? rightsecond : leftmax ;        }    }}

求數組中出現次數超過一半的元素

給定一個n個整型元素的數組a，其中有一個元素出現次數超過n / 2，求這個元素。據說是百度的一道題

分析

設置一個當前值和當前值的計數器，初始化當前值為數組首元素，計數器值為1，然后從第二個元素開始遍歷整個數組，對于每個被遍歷到的值a[i]

1 如果a[i]==currentValue，則計數器值加1

2 如果a[i] != currentValue， 則計數器值減1，如果計數器值小于0，則更新當前值為a[i]，并將計數器值重置為1

代碼

// 找出數組中出現次數超過一半的元素int Find(int* a, int n){    int curValue = a[0] ;    int count = 1 ;
    for (int i = 1; i < n; ++i)    {        if (a[i] == curValue)            count++ ;        else        {            count-- ;            if (count < 0)            {                curValue = a[i] ;                count = 1 ;            }        }    }
    return curValue ;}

另一個方法是先對數組排序，然后取中間元素即可，因為如果某個元素的個數超過一半，那么數組排序后該元素必定占據數組的中間位置。

求數組中元素的最短距離

給定一個含有n個元素的整型數組，找出數組中的兩個元素x和y使得abs(x - y)值最小

分析

先對數組排序，然后遍歷一次即可

代碼

int compare(const void* a, const void* b)
{
    return *(int*)a - *(int*)b ;
}

// 求數組中元素的最短距離void MinimumDistance(int* a, int n)
{
    // Sort    qsort(a, n, sizeof(int), compare) ;

    int i ; // Index of number 1    int j ; // Index of number 2
    int minDistance = numeric_limits::max() ;
    for (int k = 0; k < n - 1; ++k)
    {
        if (a[k + 1] - a[k] < minDistance)
        {
            minDistance = a[k + 1] - a[k] ;
            i = a[k] ;
            j = a[k + 1] ;
        }
    }

    cout << "Minimum distance is: " << minDistance << endl ;
    cout << "i = " << i << " j = " << j << endl ;
}

找出絕對值最小的元素

給定一個有序整數序列（非遞減序），可能包含負數，找出其中絕對值最小的元素，比如給定序列 -5, -3, -1, 2, 8 則返回1。

分析

由于給定序列是有序的，而這又是搜索問題，所以首先想到二分搜索法，只不過這個二分法比普通的二分法稍微麻煩點，可以分為下面幾種情況

如果給定的序列中所有的數都是正數，那么數組的第一個元素即是結果。

如果給定的序列中所有的數都是負數，那么數組的最后一個元素即是結果。

如果給定的序列中既有正數又有負數，那么絕對值得最小值一定出現在正數和負數的連接處。

為什么？因為對于負數序列來說，右側的數字比左側的數字絕對值小，如上面的-5, -3, -1, 而對于整整數來說，左邊的數字絕對值小，比如上面的2, 8，將這個思想用于二分搜索，可先判斷中間元素和兩側元素的符號，然后根據符號決定搜索區(qū)間，逐步縮小搜索區(qū)間，直到只剩下兩個元素。

代碼

單獨設置一個函數用來判斷兩個整數的符號是否相同

bool SameSign(int a, int b){    if (a * b > 0)        return true;    else        return false;}

// 找出一個非遞減序整數序列中絕對值最小的數int MinimumAbsoluteValue(int* a, int n){    // Only one number in array    if (n ==1)    {        return a[0] ;    }
    // All numbers in array have the same sign    if (SameSign(a[0], a[n -1]))    {        return a[0] >=0? a[0] : a[n -1] ;    }
    // Binary search    int l =0 ;    int r = n -1 ;
    while(l < r)    {        if (l + 1 == r)        {            return abs(a[l]) < abs(a[r]) ? a[l] : a[r] ;        }
        int m = (l + r) /2 ;
        if (SameSign(a[m], a[r]))        {            r = m;            continue;        }        else        {            l = m ;            continue;        }    }}