【解法2】优化解：散列表
← 内容总览 07 / 24 下一节 → 强化讲义 · 原始转写 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照
## 【解法2】优化解：散列表
(1)使用 count 数组保存A数组中每个数出现的次数，count[i]表示i出现的次数，循环统计完count 后计算出数组S，Si 表示小于等于i的元素有多少个。然后循环扫描 B 数组看 <= 5n -Bi]的数有多少个，加到sum中，循环完后返回sum。(2）伪代码如下：
int ans ( int A [], int B [], int n )
{
int pair_count = 0 ;
int count [ 5 * n + 1 ], S [ 5 * n + 1 ]; // S[i]表示≤i的数有多少个
for ( int i = 0 ; i & lt ; = 5 * n ; i ++ )
count [ i ] = 0 ; // 初始化count数组
for ( int i = 0 ; i & lt ; n ; i ++ )
if ( A [ i ] & lt ; = 5 * n )
count [ A [ i ]] ++ ;
S [ 0 ] = count [ 0 ];
for ( int i = 1 ; i & lt ; = 5 * n ; i ++ )
S [ i ] = S [ i -1 ] + count [ i ]; // 统计S数组
for ( int j = 0 ; j & lt ; n ; j ++ )
if ( B [ j ] & lt ; = 5 * n )
pair_count = pair_count + S [ 5 * n - B [ j ]];
return pair_count ;
}
//快速排序
void Qsort ( int A [], int L , int R )
{
if ( L & gt ; = R ) return ; // 区间≤1,返回
int i = L , j = R ;
int pivot = A [ L ]; //选首元素为基准
// 不断交换左边比 pivot 大的数和右边比 pivot 小的数
while ( i & lt ; j )
{
while ( i & lt ; j & amp ; & amp ; A [ j ] & gt ; = pivot ) j -- ; // 从右找第—个 <pivot 的数
while ( i & lt ; j & amp ; & amp ; A [ i ] & lt ; = pivot ) i ++ ; // 从左找第—个 >pivot 的数
if ( i & lt ; j ) swap ( A [ i ], A [ j ]);
}
// 将基准值 A[L] 与 A[i] 交换
swap ( A [ L ], A [ i ]);
//递归处理左右两个子区间
Qsort ( A , L , i - 1 );
Qsort ( A , i + 1 , R );
}
int ans ( int A [], int n , int k )
{
Qsort ( A , 0 , n -1 );
return A [ k -1 ];
}
int ans ( int A [], int n , int k )
{
int count [ 2 * n ];
for ( int i = 0 ; i & lt ; 2 * n ; i ++ ) count [ i ] = 0 ;
for ( int i = 0 ; i & lt ; n ; i ++ ) count [ A [ i ]] ++ ;
for ( int i = 0 ; i & lt ; 2 * n ; i ++ )
{
k -= count [ i ];
if ( k & lt ; = 0 ) return i ;
}
return -1 ;
}
//快速排序 void Qsort(int A[], int L, int R)
{
if ( L & gt ; = R ) return ; //区间≤1,返回
int i = L , j = R ;
int pivot = A [ L ]; //选首元素为基准
// 不断交换左边比 pivot大的数和右边比 pivot 小的数
while ( i & lt ; j )
{
while ( i & lt ; j & amp ; & amp ; A [ j ] & gt ; = pivot ) j -- ; // 从右找第—个 <pivot 的数
while ( i & lt ; j & amp ; & amp ; A [ i ] & lt ; = pivot ) i ++ ; // 从左找第—个 >pivot 的数
if ( i & lt ; j ) swap ( A [ i ], A [ j ]);
//将基准值 A[L]与 A[i]交换
swap ( A [ L ], A [ i ]);
//递归处理左右两个子区间
Qsort ( A , L , i - 1 );
Qsort ( A , i + 1 , R );
}
void ans ( int A [], int n )
{
Qsort ( A , 0 , n -1 );
for ( int i = 0 ; i & lt ; n ; i ++ )
if ( i == 0 || A [ i ] != A [ i -1 ]) // A[i]这个元素第一次出现则输出
printf ( & quot ; % d & quot ;, A [ i ]);
}
void ans ( int A [], int n )
{
int count [ n ] _ = { 0 };
for ( int i = 0 ; i & lt ; n ; i ++ )
count [ A [ i ] -2 * n ] ++ ; //统计 A 中每个元素出现次数
for ( int i = 0 ; i & lt ; n ; i ++ )
if ( count [ i ] & gt ; 0 )
printf ( & quot ; % d & quot ;, i + 2 * n ); // 若 count[i]>0 说明 i+2n 出现过
}
int ans ( int A [], int n , int k )
{
int m ; //m是本次遍历选择元素数
int m_max = 0 ; // m_max初值为0
for ( int i = 0 ; i & lt ; n ; i ++ ){ //A[i]为本次枚举最小元素
m = 0 ; // 每次枚举时都需要清空m
for ( int j = 0 ; j & lt ; n ; j ++ )
if ( A [ j ] & gt ; = A [ i ] & amp ; & amp ; A [ j ] & lt ; = A [ i ] + k )
m ++ ; // A[j]处于选择范围则m++
m_max = max ( m_max , m ); // 如果m大则更新m_max
}
return m_max ; // 输出最大m值
}
//快速排序
void Qsort ( int A [], int L , int R )
{
int i = L , j = R ; if ( L & gt ; = R ) return ; //区间≤1,返回
int pivot = A [ L ]; //选首元素为基准
// 不断交换左边比 pivot 大的数和右边比 pivot 小的数
while ( i & lt ; j )
{
while ( i & lt ; j & amp ; & amp ; A [ j ] & gt ; = pivot ) j -- ; // 从右找第—个 <pivot 的数
while ( i & lt ; j & amp ; & amp ; A [ i ] & lt ; = pivot ) i ++ ; // 从左找第—个 >pivot 的数
王 if ( i & lt ; j ) swap ( A [ i ], A [ j ]);
//将基准值A[L] 与A[i] 交换
swap ( A [ L ], A [ i ]);
//递归处理左右两个子区间
Qsort ( A , L , i - 1 );
Qsort ( A , i + 1 , R );
}
int ans ( int A [], int n , int k )
{
int m ; //m是本次遍历选择元素数
int m_max = 0 ; // m_max初值为0
int i = 0 , j = 0 ; //A[i~j]是选择的元素
Qsort ( A , 0 , n -1 ); //快速排序
for ( i = 0 ; i & lt ; n ; i ++ ){
while ( j + 1 & lt ; n & amp ; & amp ; A [ j + 1 ] & lt ; = A [ i ] + k )
j ++ ; // j+1也在范围内，j后移
m = j - i + 1 ; //求出m
m_max = max ( m_max , m ); // 如果m大则更新m_max
if ( j == n -1 ) break ; // j 已到末尾
}
return m_max ; //输出最大m值
}
}
int ans ( int A [], int n , int k )
{
int m = 0 ;
int m_max = 0 ; // m_max 初值为 0
int B [ maxn ];
memset ( B , 0 , sizeof ( B ));
for ( int i = 0 ; i & lt ; n ; i ++ ) B [ A [ i ]] ++ ; // A[i]出现次数+1
int L = 0 , R = 0 ;
for ( R = 0 ; R & lt ; n ; R ++ )
{
// m 加上 B[R]
if ( R - L & gt ; k )
{ // 如果范围差大于 k 则 L 右移
m -= B [ L ]; // [L+1,R],减 B[L]
L ++ ;
}
m_max = max ( m_max , m ); // 如果 m 大则更新 m_max
}
return m_max ;
} 彩
← 内容总览 07 / 24 下一节 →