习题2-16
← 内容总览 08 / 24 下一节 → 原始讲义 · 非增强校订版 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照
## 习题2-16
(15 分）在数组中，某个数字减去它右边的数字得到一个数对之差。求所有数对之差的最大值。例如，在数组{2,4,1,16,7,5,11,9}中，数对之差的最大值是11，是16 减去5的结果。设计一个在时间上尽可能高效的算法输出所有数对之差的最大值。
(1)给出算法的基本设计思想。
(2)根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
(3)说明你所设计算法的时间和空间复杂度。
<table><tr><td rowspan=1 colspan=1></td><td rowspan=1 colspan=1>做题思路</td><td rowspan=1 colspan=1>时间复杂度</td><td rowspan=1 colspan=1>空间复杂度</td><td rowspan=1 colspan=1>得分</td></tr><tr><td rowspan=1 colspan=1>暴力解</td><td rowspan=1 colspan=1>枚举</td><td rowspan=1 colspan=1>O(n²)</td><td rowspan=1 colspan=1>0(1)</td><td rowspan=1 colspan=1>13</td></tr><tr><td rowspan=1 colspan=1>优化解</td><td rowspan=1 colspan=1>预处理</td><td rowspan=1 colspan=1>O(n)</td><td rowspan=1 colspan=1>0(1)</td><td rowspan=1 colspan=1>15</td></tr></table>
<!-- page 52 -->
(1）使用两层循环，外层i遍历数组，内层j再从i+1开始遍历一次整个数组（默认i<j），A[i]是数对中的前一个元素，A[j]即是数对中的后一个元素，求出m=A[i]和A[j]之差的绝对值，输出最大的m。
(2) 伪代码如下：
int ans ( int A [], int n )
{
int m ; // m 是数对之差的绝对值
int m_max = INT_MIN ; // m_max 初值为最小 int
for ( int i = 0 ; i & lt ; n -1 ; i ++ ) // 枚举前一个元素
for ( int j = i + 1 ; j & lt ; n ; j ++ ) // 枚举后一个元素
{
m = A [ i ] - A [ j ]; // A[i] 和 A[j] 之差
m_max = max ( m_max , m ); // 如果 m 大则更新 m_max
}
return m_max ; // 输出最大 m 值
}
( 3 ) // 时间复杂度： O(n²) 空间复杂度：O(1)
int ans ( int A [], int n )
{
int m_max = INT_MIN ; // m_max初值为最小int
int m ;
//预处理，数组B保存最大值
int B [ n ];
B [ 0 ] = A [ 0 ];
for ( int i = 1 ; i & lt ; n ; i ++ )
B [ i ] = max ( A [ i ], B [ i -1 ]);
for ( int i = 1 ; i & lt ; n ; i ++ )
m_max = max ( m_max , B [ i -1 ] - A [ i ]); //如果B[i]-A[i]更大则更新m_max
return m_max ; //输出最大m值
}
int ans ( int A [], int n )
{
int m_max = INT_MIN ; // m_max 初值为最小 int
int m ;
int t = A [ 0 ]; // t 来保存 A[i] 之前的最大值，初值为
A [ 0 ]
for ( int j = 1 ; j & lt ; n ; j ++ ) //后一个元素下标从 1 开始
{
m = t - A [ j ];
m_max = max ( m_max , m ); // 如果 m 大则更新 m_max
t = max ( t , A [ j ]); // 如果 A[j] 大则更新 t
return m_max ; // 输出最大 m 值
}
}
int countoccurrences ( int A [], int n , int x )
{
int count = 0 ; //初始化计数器
//枚举，遍历整个数组 A
for ( int i = 0 ; i & lt ; n ; i ++ )
{
//如果当前元素等于 x，计数器加一
if ( A [ i ] == x ) count ++ ;
}
return count ; // 返回最终计数值
}
( 3 ) // 时间复杂度：O(n) 空间复杂度：O(1)
//折半查找模板二：查找第一个大于或等于 x 的元素的下标
int B_Search ( int A [], int L , int R , int x )
{
int mid ;
while ( L & lt ; R )
mid = ( L + R ) / 2 ;
if ( A [ mid ] & gt ; = x ) R = mid ;
else L = mid + 1 ;
}
return L ;
}
int countoccurrences ( int A [], int n , int x ) {
// 1.查找最左侧的 x 下标
int left = B_Search ( A , 0 , n -1 , x );
// 2.如果它不等于 x 则说明数组中没有 x
if ( A [ left ] != x ) return 0 ;
// 3.查找最左侧的 x 下标
int right = B_Search ( A , 0 , n -1 , x + 1 );
if ( A [ right ] & gt ; = x + 1 )
right -- ;
// 4. 次数 = right - left + 1
return right - left + 1 ;
( 3 ) // 时间复杂度：O(logn) an 空间复杂度：O(1)
void ans ( int A [], int n , int p )
{
int B [ n ];
for ( int i = 0 ; i & lt ; p ; i ++ )
B [ i + n - p ] = A [ i ];
for ( int i = p ; i & lt ; n ; i ++ )
B [ i - p ] = A [ i ];
for ( int i = 0 ; i & lt ; n ; i ++ )
printf ( & quot ; % d & quot ;, B [ i ]);
}
( 3 ) // 时间复杂度：O(n) 空间复杂度：O(n)
void Reverse ( int A [], int L , int R )
{
int num = ( R - L + 1 ) / 2 ;
for ( int i = 0 ; i & lt ; num ; i ++ )
swap ( A [ L + i ], A [ R - i ]);
}
void ans ( int A [], int n , int p )
{
Reverse ( A , 0 , p -1 ); //翻转A[0~p-1]
Reverse ( A , p , n -1 ); // 翻转A[p~n-1]
Reverse ( A , 0 , n -1 ); //翻转A[0~n-1]
for ( int i = 0 ; i & lt ; n ; i ++ )
printf ( & quot ; % d & quot ;, A [ i ]); // 输出翻转后的数组
}
void Qsort ( int A [], int L , int R )
{
if ( L & gt ; = R )
return ; // 当前区间元素个数<=1则退出
int pivot , i = L , j = R ; // i和j是左右两个数组下标移动
pivot = A [ L ]; // pivot作为基准值参与比较
while ( i & lt ; j ){
while ( i & lt ; j & amp ; & amp ; A [ j ] & gt ; = pivot )
j -- ;
while ( i & lt ; j & amp ; & amp ; A [ i ] & lt ; = pivot )
i ++ ;
if ( i & lt ; j )
// A[j]<pivot, A[i]>pivot
}
swap ( A [ L ], A [ i ]); //将基准值放入他的最终位置
Qsort ( A , L , i -1 ); // 递归处理左区间
Qsort ( A , i + 1 , R ); // 递归处理右区间
}
int ans ( int A [], int B [], int n )
{
int C [ 2 * n ];
for ( int i = 0 ; i & lt ; n ; i ++ )
{
C [ i ] = A [ i ];
C [ n + i ] = B [ i ];
}
Qsort ( C , 0 , 2 * n -1 ); //快速排序处理C[0]~C[2n-1]
return C [ n -1 ]; // 中位数输出C[n-1]
}
( 3 ) // 时间复杂度：O(nlogn) 空间复杂度：O(n)
int ans ( int A [], int B [], int n )
{
int C [ 2 * n ];
int i = 0 , j = 0 , k = 0 ;
while ( i & lt ; n & amp ; & amp ; j & lt ; n )
if ( A [ i ] & lt ; B [ j ])
C [ k ++ ] = A [ i ++ ];
else
C [ k ++ ] = B [ j ++ ];
while ( i & lt ; n ) C [ k ++ ] = A [ i ++ ];
while ( j & lt ; n ) C [ k ++ ] = B [ j ++ ];
return C [ n -1 ]; // 输出C[n-1]
}
( 3 ) // 时间复杂度：O(n) 空间复杂度：O(n)
int ans ( int A [], int B [], int n )
{
int i = 0 , j = 0 , k ;
for ( k = 1 ; k & lt ; n ; k ++ )
即为中位数 。
if ( A [ i ] & lt ; B [ j ]) i ++ ;
else j ++ ;
return min ( A [ i ], B [ j ]);
}
( 3 ) // 时间复杂度：O(n) 空间复杂度：O(1)
← 内容总览 08 / 24 下一节 →