【解法1】暴力解：枚举法
强化讲义 · 原始转写 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照
## 【解法1】暴力解：枚举法
(1) 对每个元素 A[i]，计算比它小的元素个数 count，如果恰好为 n/2，则为中位数。
(2) 伪代码如下：
int ans(int A[], int n)
{
for (int i = 0; i < n; i++)
{
int count = 0;
for (int j = 0; j < n; j++)
if (A[j] < A[i]) count++;
if (count == n / 2) return A[i];
}
} return -1;
//快速排序函数
void Qsort(int A[], int L, int R)
{
if (L >= R) return; //区间≤1,返回
int i = L, j = R;
//选首元素为基准
// 不断交换左边比 pivot 大的数和右边比 pivot 小的数
while (i < j)
{
while (i < j && A[j] >= pivot) j--; // 从右找第—个 <pivot 的数
while (i < j && A[i] <= pivot) i++; // 从左找第—个 >pivot 的数
//将基准值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 < n; i++)
count[A[i] + n]++;
int sum = 0; KX //累计到目前为止已经是第几小的数了
for (int i = 0; i < 2*n+1; i++)
{
sum = sum + count[i];
if (sum > n/2)
return i-n;
}
}
void Qsort_Select(int A[], int L, int R)
{
if (L >= R) return; //区间≤1,返回
int i = L, j = R;
int pivot = A[L]; //选首元素为基准
不断交换左边比pivot 大的数和右边比 pivot 小的数
while (i < j)
{
while (i < j && A[j] >= pivot) j--; // 从右找第—个 ≤pivot 的数
if (i < j) swap(A[i], A[j]);
}
//将基准值A[L] 与A[i]交换
swap(A[L], A[i]);
if (L <= n/2 && i-1 >= 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];
}
//快速排序函数
void Qsort(int A[], int L, int R)
{
if (L >= R) return; //区间≤1,返回
int i = L, j = R;
int pivot = A[L]; // 选首元素为基准
// 不断交换左边比 pivot 大的数和右边比 pivot 小的数
while (i < j)
{
while (i < j && A[i] <= pivot) i++; // 从左找第个 >pivot 的数
if (i < 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<0; i<n/2; i++)
swap(A[i], A[n-i-1]);
输出数组 A
}
void Multiointers(int A[], int L, int R, int k)
{
if (L>=R) return; // 区间≤1，退出
int pivot, i=L, j=R; // i,j 为左右指针
pivot=k;
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]); /7A[j]>k,A[i]<k
}
}
int ans(int A[], int n, int k)
{
Multiointers(A, 0, n-1, k);
按顺序输出A数组
}
int ans(int A[], int n, int key)
{
for (int i = 0; i < n; i++)
if (A[i] == key) return i;
return -1;
}
//在升序数组中查找
int B_Search_up(int A[],int L, int R, int x)
{
int mid;
// 区间非空则继续
{
mid = (R + L) / 2; //防溢出
return mid; //找到了，立即返回
else
if (x < A[mid]) R = mid - 1;
else L = mid + 1; // x 在右半边，mid 被排除
}
return -1; //循环结束，说明没找到
//在降序数组中查找
int B_Search_down(int A[], int L, int R, int x))
{
int mid;
while (L <= R) // 区间非空则继续
{
mid = (R + L) / 2; //防溢出
if (A[mid] == x)
return mid; //找到了,立即返回
else
if (x > 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;
}
}
int ans(int a[], int b[], int n)
{
int D_min = INT_MAX; // D_min初值为最大
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
D_min = min(D_min, abs(a[i] - b[j]));
return D_min;
}
int ans(int a[], int b[],int n)
{
int D_min = INT_MAX; // D_min初值为最大
int i = 0, j = 0;
while (i<n && j<n)
{
D_min = min(D_min, abs(a[i] - b[j]));
if (a[i]<b[j]) i++;
else j++;
}
return D_min;
}