【解法1】暴力解：枚举最小正整数
原始讲义 · 非增强校订版 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照
## 【解法1】暴力解：枚举最小正整数
(1)可以证明最小未出现的正整数t一定≤n+1(因为如果t>n+1，则1\~t-1都会出现一次，但只有n个整数，所以t-1≤n，即t≤n+1），枚举所有可能的未出现最小正整数，扫描一次数组判断是否符合。
(2) 伪代码如下：
int ans(int A[], int n)
{
for (int i=1; i<=n+1; i++)
{
bool flag=false;
for (int j=0; j<n; j++)
if (i==A[j])
flag=true;
if (flag==false)
return i;
}
}
// 先假设i未出现
//此时i出现了，f1ag变成true
//若i未出现过则输出i
(3) // 时间复杂度：O(n²) 空间复杂度：O(1)
void Qsort(int A[], int L, int R)
{N
if (L>=R)
return;
int pivot, i=L, j=R;
}
// 当前区间元素个数<=1则退出
// i和j是左右两个数组下标移动
pivot=A[L]; // pivot作为基准值参与比较
while (i<j){
while (i<j && A[j]>=pivot)
j--;
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; //输出最小未出现正整数
}
(3) // 时间复杂度：O(nlogn) 空间复杂度：O(logn)
int ans(int A[],int n)
{
int count[n+2]={0}; // 0~n+1
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
}
(3) // 时间复杂度：O(n) 空间复杂度：O(n)
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<1; 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)
{
int D, D_min=INT_MAX; // 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
while (k < l - 1 && DD(A[i], B[j], C[k+1])<D)
D = DD(A[i], B[j], C[++k]); // 更新下标k和距离D
D_min = min(D_min, D); // 更新最小D值
}
return D_min; // 输出最小D值
}
(3) // 时间复杂度： O(mn) 或O(n²) 空间复杂度：O(1)
int lowerBound(int A[], int n, int x)
{
int L = 0, R = n;
while (L < R)
{
int mid = L + (R - L) / 2;
if (A[mid] < x) L = mid + 1;
else R = mid;
}
return L;
}
int DD(int a, int b, int c)
{
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;
for (int i = 0; i < n; i++)
{
int jb = lowerBound(B, m, A[i]);
int kc = lowerBound(C, l, A[i]);
for (int db = -1; db <= 0; db++)
for (int dc = -1; dc <= 0; dc++)
{
int j = jb + db, k = kc + dc;
if (j >= 0 && j < m && k >= 0 && k < l)
D_min = min(D_min, DD(A[i], B[j], C[k]));
}
}
return D_min;
}
(3) // 时间复杂度: O(n *(logm + logl))或O(nlogn) 空间复杂度：O(1)
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<1)
{
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值
}
(3) // 时间复杂度: O(m + n + l)或O(n) 空间复杂度：O(1)
// 暴力破解法实现
void CalMulMax(int A[], int res[], int n)
{
for(int i = 0; i < n; i++)
{ //遍历每个起始位置
o m
int maxMu] = A[i] * A[i]; //初始化
for(int j = i; j < n; j++)
{ // 遍历所有j >= i
int currentMu] = 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];
int c[n];
// 从后向前遍历，填充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
}