【解法2】暴力解：快速排序，然后扫描一遍数组
强化讲义 · 原始转写 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照
## 【解法2】暴力解：快速排序，然后扫描一遍数组
(1)先对数组A快速排序得到升序序列，然后遍历数组找到第一个未出现的最小正整数。
(2) 伪代码如下：
<!-- suspect-code -->
> [!warning] 这段代码需要核对（原文第 94 页）
> OCR 体检未通过：花括号不平衡。扫描件的两栏排版（代码 + 右侧注释）有时会被交错读取，产生看起来合理但语义错误的代码。背之前请对照原文。
void Qsort(int A[], int L, int R)
{
if (L>=R)
return; // 区间≤1,退出
int pivot, i=L, j=R; // i,j 为左右指针
pivot=A[L]; // pivot 为基准
while (i<j){
while (i<j && A[j]>=pivot)
while (i<j && A[i]<=pivot)
i++;
if(i<j)
swap(A[i], A[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 n)
{
Qsort(A, 0, n-1);
int t=1; // 假设初始最小未出现正整数t=1
for (int i=0; i<n; i++)
if (A[i]==t)
t++; // t已出现，此时最小未出现正整数是t+1
return t; //输出最小未出现正整数
} 丝研
int ans(int A[],int n)
{
int count[n+2]={0};
for (int i=0; i<n; i++) // 扫描数组A
if (A[i]>0 && A[i]<=n+1) // 当0<A[i]<=n+1时才修改
count[A[i]]++;
for (int j=1; j<=n+1; j++) // 扫描count数组
if (count[j]==0) //j未出现过，是最小未出现正整数
return j; //输出j
}
int ans(int A[],int n,int B[],int m,int C[],int l)
{
int D_min=INT_MAX, D; // D_min初值为最大整数
for (int i=0; i<n; i++)
for (int j=0; j<m; j++)
for (int k=0; k<l; k++){ // 三重循环枚举abc
D=abs(A[i]-B[j])+abs(B[j]-C[k])+abs(C[k]-A[i]);
D_min=min(D_min, D); // 更新最小D值
}
return D_min; //输出最小D值
}
int DD(int a,int b,int c)
{ DD(a,b,c)=|a-b|+|b-c|+|b-a|
return abs(a-b)+abs(b-c)+abs(c-a);
}
int ans(int A[],int n,int B[],int m,int C[],int l)
{
// D_min初值为最大整数
int k=0;
for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
{ //两重循环枚举a、b
D = DD(A[i], B[j], C[k]); //枚举a、b得到的初始D
D = DD(A[i],B[j],C[++k]); // 更新下标k和距离D
D_min = min(D_min, D); //更新最小D值
}
} return D_min; // 输出最小D值
int DD(int a,int b,int c) // DD(a,b,c)=|a-b|+|b-c|+|b-a|
{
return abs(a-b)+abs(b-c)+abs(c-a);
}
int D, D_min=INT_MAX; √ D_min初值为最大整数
for (int i=0; i<n; i++)
{
int j=B_Search(B, 0, m-1, A[il); // 在B中根据A[i]折半查找
int k=B_Search(C, 0, l-1, A[i]); // 在C中根据A[i]折半查找
if (j>=0 && k>=0)
D_min=min(D_min, DD(A[i], B[j], C[k]));
if (j+1<m && k>=0)
D_min=min(D_min, DD(A[i], B[j+1], C[k]));
if (j>=0 && k+1<l)
if (j+1<m && k+1<l)
D_min=min(D_min, DD(A[i], B[j+1],C[k+1]));
}
return D_min; // 输出最小D值
int DD(int a,int b,int c) DD(a,b,c)=|a-b|+|b-c|+|b-a|
{
return abs(a-b)+abs(b-c)+abs(c-a);
}
int ans(int A[],int n,int B[],int m,int C[],int l)
{
int D_min=INT_MAX; // D_min初值为最大整数
int i=0, j=0, k=0; //数组A、B、C的下标i、j、k
while(i<n && j<m && k<l)
{
D_min=min(D_min, DD(A[i],B[j], C[k])); // 更新D_min
if (A[i]<B[j] && A[i]<C[k])
i++;
else
if (B[j]<C[k])
j++;
else
k++;
}
return D_min; // 输出最小D值
}
//暴力破解法实现
void CalMulMax(int A[], int res[], int n)
{
for(int i = 0; i < n; i++)
{ // 遍历每个起始位置i
int maxMul = A[i] * A[i]; //初始化
for(int j = i; j < n; j++)
{ // 遍历所有j >= i
int currentMul = A[i] * A[j];
if (currentMul > maxMul) //当前乘积更大，更新
maxMul = currentMul;
}
res[i] = maxMul; // 将最大乘积存入res[i]
} 有机考研
输出数组res
}
// 使用辅助数组B和C的实现
void CalMulMax(int A[], int res[], int n)
{
int B[n];// B[i]表示A[i..n-1]中的最大值
int C[n];// C[i]表示A[i..n-1]中的最小值
//从后向前遍历，填充B和C数组
B[n-1] = A[n-1];
C[n-1] = A[n-1];
for(int i = n-2; i >= 0; i--)
{
B[i] = max(B[i+1], A[i]);
C[i] = min(C[i+1],A[i]);
}
// 计算res数组，最大值只可能是A[i]*B[i]或A[i]*C[i]
for(int i = 0; i < n; i++)
res[i] = max(A[i]*B[i], A[i]*C[i]);
输出数组res
}
//使用辅助变量B和C的实现
void CalMulMax(int A[], int res[], int n)
{
int B; // B表示A[i..n-1]中的最大值
int C; // C表示A[i.n-1]中的最小值
B = A[n-1];
C = A[n-1];
res[n-1] = A[n-1]*A[n-1];
//计算res数组，最大值只可能是A[i]*B[i]或A[i]*C[i]
for(int i = n-2; i >= 0; i--)
{
B = max(B, A[i]);
C = min(C, A[i]);
res[i] = max(A[i]*B, A[i]*C);
}
输出数组res
}