【面接問題-プログラミング】配列の差が最も大きい2つの数を検索

1014 ワード

テーマ:1つの関数を書いて、1つの配列の中で右から左の差を減らす最大の2つの数を探すことを実現します.右は、現在の配列の右にあるすべての数です.
考え方1:最初に思いついたのは配列全体をループし、右のすべての数字から現在の位置の数を減算し、最大差の2つの数を記録することです.時間複雑度O(N*N)
考え方2:最大差値は、現在の数から左の最小数の中で最大の値を減算することができます.時間複雑度O(N)
構想2の関数:
template <class T>
void FindMaxDifference2(const T array[], const int arraySize, T &leftNum, T &rightNum)
{
    assert(arraySize >= 2);  //        2   

    //                
    leftNum = array[0];
    rightNum = array[1];
    T difference = rightNum - leftNum;  //         
    T minNum = leftNum > rightNum ? rightNum : leftNum;   //         

    for (int i = 2; i < arraySize; i++)
    {
        //                   ,     ,       
        if (array[i] - minNum > difference)
        {
            leftNum = minNum;
            rightNum = array[i];
            difference = array[i] - minNum;
        }

        if (array[i] < minNum)    //              ,        
        {
            minNum = array[i];
        }
    }
}