統計一個數字在排序數組中出現的次數。 輸入： 每個測試案例包括兩行： 第一行有1個整數n，表示數組的大小。1<=n <= 10^6。 第二行有n個整數，表示數組元素，每個元素均為int。 第三行有1個整數m，表示接下來有m次查詢。1<=m<=10^3。 下面有m行，每行有一個整數k，表示要查詢的數。 輸出： 對應每個測試案例，有m行輸出，每行1整數，表示數組中該數字出現的次數。 樣例輸入： 8 1 2 3 3 3 3 4 5 1 3 樣例輸出： 4 思想：使用二分法找到具體數字的位置，然後需要前後掃描來確定數字的個數~^_^ 代碼AC： [cpp] // 用2分法！！ ^_^ #include <stdio.h> #include <stdlib.h> int main() { long int n, i, cou, mid, low, high; int m, *num, k; while( scanf( "%ld", &n ) != EOF ) { num = ( int* )malloc( sizeof( int ) * n ); for( i = 0; i < n; i++ ) { scanf("%d", &num[i]); } scanf("%d", &m); while( m-- ) { scanf("%d", &k); low = 0; high = n - 1; while( low <= high ) { mid = ( low + high ) / 2; if( k == num[mid] ) { break; } else if( k > num[mid] ) { low = mid + 1; } else { high = mid - 1; } } cou = 0; i = mid; while( i < n ) { if( num[i] == k ) { cou++; i++; } else { break; } } i = mid - 1; while( i >= 0 ) { if( num[i] == k ) { cou++; i--; } else { break; } } printf("%d\n", cou); } } return 0; }
