ソート配列に数値が表示される回数(C/C++)

1315 ワード

配列に数が複数回現れることは明らかです.
配列をソートするには、時間と効率が必要です.必ず二分で検索します.ただし、ここで検索する要素は複数回現れる可能性があります.古典的な二分検索を少し変える必要があります
非再帰アルゴリズムは次のとおりです.
#include 
using namespace std;

/*            ,     -1。
wantLeft true:     val;         */
int repeatedTimesOfNumber( int *arr, int left, int right, int val, bool wantLeft ) {
    if( arr == NULL )
        return -1;
    int last=-1; /*             */
    int mid = ( left + right ) / 2;
    while( left <= right ) {
        if( val > arr[mid] )
            left = mid + 1;
        else if( val < arr[mid] )
            right = mid - 1;
        else {
            last = mid;
            if( wantLeft ) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        mid = ( left + right ) / 2;
    } // while
    return last;
}

int main()
{
    int arr[] = {1,2,3,3,3,3,4,5};
    int lowerPos = repeatedTimesOfNumber( arr, 0, sizeof(arr)/sizeof(arr[0]) - 1, 3, true );
    int upperPos = repeatedTimesOfNumber( arr, 0, sizeof(arr)/sizeof(arr[0]) - 1, 3, false );
    cout << "lower position: " << lowerPos << endl;
    cout << "upper position: " << upperPos << endl;
    cout << upperPos - lowerPos + 1 << endl;

    return 0;
}