百度地图实时街景怎么移动/怎么样关键词优化

题目：

给出一个O(n)时间的算法，在给定一个有n个不同数字的集合S以及一个正整数k<=n后，它能确定出S中最接近其中位数的k个数

思考：

step1：求出数组的中位数的值O(n)

step2：计算数组每个数与中位数差的绝对值，存于另一个数组B中O(n)

step3：求出数组B中第k小的数ret O(n)

step4：计算数组S中与ret差的绝对值小于ret的数并输出O(n)

其中，step4也可以通过划分的方法找出数组S中与ret差的绝对值小于ret的数

代码：

#include <iostream>
using namespace std;int length_A;
void Print(int *A)
{int i;for(i = 1; i <= length_A; i++)cout<<A[i]<<' ';cout<<endl;
}
/*************最坏情况线性时间的选择**************************************************/
//已经出现很多次了，不解释
int Partition(int *A, int p, int r)
{int x = A[r], i = p-1, j;for(j = p; j < r; j++){if(A[j] <= x){i++;swap(A[i], A[j]);}}swap(A[i+1], A[r]);return i+1;
}
int Select(int *A, int p, int r, int i);
//对每一组从start到end进行插入排序，并返回中值
//插入排序很简单，不解释
int Insert(int *A, int start, int end, int k)
{int i, j;for(i = 2; i <= end; i++){int t = A[i];for(j = i; j >= start; j--){if(j == start)A[j] = t;else if(A[j-1] > t)A[j] = A[j-1];else{A[j] = t;break;}}}return A[start+k-1];
}
//根据文中的算法，找到中值的中值
int Find(int *A, int p, int r)
{int i, j = 0;int start, end, len = r - p + 1;int *B = new int[len/5+1];//每5个元素一组，长度为start到end，对每一组进行插入排序，并返回中值for(i = 1; i <= len; i++){if(i % 5 == 1)start = i+p-1;if(i % 5 == 0 || i == len){j++;end = i+p-1;//对每一组从start到end进行插入排序，并返回中值,如果是最后一组，组中元素个数可能少于5int ret = Insert(A, start, end, (end-start)/2+1);//把每一组的中值挑出来形成一个新的数组B[j] = ret;	}}//对这个数组以递归调用Select()的方式寻找中值int ret = Select(B, 1, j, (j+1)/2);//delete []B;return ret;
}
//以f为主元的划分
int Partition2(int *A, int p, int r, int f)
{int i;//找到f的位置并让它与A[r]交换for(i = p; i < r; i++){if(A[i] == f){swap(A[i], A[r]);break;}}return Partition(A, p, r);
}
//寻找数组A[p..r]中的第i大的元素，i是从1开始计数，不是从p开始
int Select(int *A, int p, int r, int i)
{//如果数组中只有一个元素，则直接返回if(p == r)return A[p];//根据文中的算法，找到中值的中值int f = Find(A, p, r);//以这个中值为主元的划分，返回中值在整个数组A[1..len]的位置//因为主元是数组中的某个元素，划分好是这样的，A[p..q-1] <= f < A[q+1..r]int q = Partition2(A, p, r, f);//转换为中值在在数组A[p..r]中的位置int k = q - p + 1;//与所寻找的元素相比较if(i == k)return A[q];else if(i < k)return Select(A, p, q-1, i);else//如果主元是数组中的某个元素，后面一半要这样写return Select(A, q+1, r, i-k);//但是如果主元不是数组中的个某个元素，后面一半要改成Select(A, q, r, i-k+1)
}
int main()
{int k, i;while(cin>>length_A>>k){if(k > length_A){cout<<"error:k > length_A"<<endl;continue;}//生成随机数据int *A = new int[length_A+1];for(i = 1; i <= length_A; i++)A[i] = rand() % 100;Print(A);//计算中位数int mid = Select(A, 1, length_A, (length_A+1)/2);//计算每个数与中位数的距离int *B = new int[length_A+1];for(i = 1; i <= length_A; i++)B[i] = abs(A[i] - mid);//选择第k小的数int ret = Select(B, 1, length_A, k);//求出数组是与中位数距离小于ret的数，并输出for(i = 1; i <= length_A; i++)if(abs(A[i] - mid) <= ret)cout<<A[i]<<' ';cout<<endl;delete []A;}return 0;
}