ソート配列に数値が表示される回数(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;
}