【解法3】优化解：散列表
← 内容总览 05 / 24 下一节 → 原始讲义 · 非增强校订版 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照
## 【解法3】优化解：散列表
(1)设置count数组表示某个数出现的次数，循环遍历数组A并更新count数组，访问A[i]时如果发现count[A[i]]已经>0说明之前A[i]已经出现过，输出A[i]。如果最终都没有发现有重复元素，则输出-1。
(2) 伪代码如下：
int ans ( int A [], int n )
{
int count [ n ] = { 0 };
for ( int i = 0 ; i & lt ; n ; i ++ )
{
if ( count [ A [ i ]] & gt ; 0 ) return A [ i ];
count [ A [ i ]] ++ ;
} return -1 ; . c
}
int ans ( int A [], int n )
{
for ( int i = 0 ; i & lt ; n ; i ++ )
{
int count = 0 ;
for ( int j = 0 ; j & lt ; n ; j ++ )
if ( A [ j ] & lt ; A [ i ]) count ++ ;
if ( count == n / 2 ) return A [ i ];
return -1 ;
}
}
( 3 ) // 时间复杂度：O(n²) 空间复杂度：O(1)
//快速排序函数
void Qsort ( int A [], int L , int R )
{
if ( L & gt ; = R ) return ; //区间内元素个数为0或 1，自然有序，递归
终止
int i = L , j = R ;
int pivot = A [ L ]; // 选取区间第一个元素作为基准
// 不断交换左边比 pivot 大的数和右边比 pivot 小的数
while ( i & lt ; j )
o m
{
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 )
{
Qsort ( A , 0 , n -1 );
return A [ n / 2 ];
}
}
( 3 ) // 时间复杂度：O(nlogn) 空间复杂度：O(logn)
int ans ( int A [], int n )
{
int count [ 2 * n + 1 ] = { 0 }; //散列表记录x-n出现的次数
for ( int i = 0 ; i & lt ; n ; i ++ )
count [ A [ i ] + n ] ++ ;
int sum = 0 ; //累计到目前为止已经是第几小的数了
for ( int i = 0 ; i & lt ; 2 * n + 1 ; i ++ )
{
sum = sum + count [ i ];
if ( sum & gt ; n / 2 )
return i - n ;
}
}
( 3 ) // 时间复杂度：O(n) 空间复杂度：O(n)
void Qsort_Select ( int A [], int L , int R )
{
if ( L & gt ; = R ) return ; //区间内元素个数为 0 或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 ]);
if ( L & lt ; = n / 2 & amp ; & amp ; i -1 & gt ; = n / 2 )
Quick_Select ( A , L , i -1 , n ); // 左区间包括中位数
else
Quick_Select ( A , i + 1 , R , n ); // 右区间包括中位数
}
int ans ( int A [], int n )
{
Quick_Select ( A , 0 , n -1 , n );
return A [ n / 2 ];
}
( 3 ) // 时间复杂度：O(n) 空间复杂度：O(logn)
//快速排序函数
void Qsort ( int A [], int L , int R )
{
if ( L & gt ; = R ) return ;
终止
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 );
for ( int i & lt ; 0 ; i & lt ; n / 2 ; i ++ )
swap ( A [ i ], A [ n - i -1 ]);
输出数组 A
}
}
( 3 ) // 时间复杂度： O(nlogn) 空间复杂度：O(logn)
void Multiointers ( int A [], int L , int R , int k )
{
if ( L & gt ; = R ) return ; // 当前区间元素个数<=1则退出
int pivot , i = L , j = R ; // i和j是左右两个数组下标移动
pivot = k ;
while ( i & lt ; j )
{
while ( i & lt ; j & amp ; & amp ; A [ j ] & lt ; = pivot ) j -- ; //右边<=则不处理
while ( i & lt ; j & amp ; & amp ; A [ i ] & gt ; = pivot ) i ++ ; //左边>=则不处理
if ( i & lt ; j ) swap ( A [ i ], A [ j ]); // A[j]>k, A[i]<k
}
}
int ans ( int A [], int n , int k )
{
Multiointers ( A , 0 , n -1 , k );
按顺序输出A数组
}
( 3 ) // 时间复杂度：O(n) 空间复杂度：O(1)
int ans ( int A [], int n , int key )
{
for ( int i = 0 ; i & lt ; n ; i ++ )
if ( A [ i ] == key ) return i ;
return -1 ;
}
( 3 ) // 时间复杂度：O(n) 空间复杂度：O(1)
//在升序数组中查找
int B_Search_up ( int A [], int L , int R , int x )
{
int mid ;
while ( L & lt ; = R ) //只要区间不为空就继续
{
mid = ( R + L ) / 2 ; //防溢出 首计算
if ( A [ mid ] == x )
return mid ; // 找到了，立即返回
else
if ( x & gt ; A [ mid ]) R = mid - 1 ;
else L = mid + 1 ; // x 在右半边，mid 被排除
}
return -1 ; //循环结束，说明没找到
//在降序数组中查找 m
int B_Search_down ( int A [], int L , int R , int x )
{
int mid ;
while ( L & lt ; = R ) // 只要区间不为空就继续
{
mid = ( R + L ) / 2 ; //防溢出
if ( A [ mid ] == x )
return mid ; //找到了，立即返回
}
}
}
else
if ( x & lt ; A [ mid ]) R = mid - 1 ;
else L = mid + 1 ; // x 在右半边，mid 被排除
}
return -1 ; //循环结束，说明没找到
int ans ( int A [], int n , int key )
{
int i ;
i = B_Search_down ( A , 0 , n / 2-1 , key ); // 折半查找降序序列
if ( i != -1 )
return i ; //折半查找降序成功
i = B_Search_up ( A , n / 2 , n -1 , key ); //折半查找升序序列
return i ;
( 3 ) // 时间复杂度：O(logn) 空间复杂度：O(1)
← 内容总览 05 / 24 下一节 →